Given a binary tree, count all subtrees in it such that every node in the subtree have same value.
There are 6 subtrees having same data
A simple solution would be to consider every node and check if all nodes present in the subtree rooted at current node have same values or not. The time complexity of this solution is O(n2).
We can solve this problem in linear time. The idea is traverse the tree in postorder fashion. Then by comparing return values of left subtree and right subtree, we can easily check if subtree rooted at any node have same values or not.
C++ implementation –
// Data structure to store a Binary Tree node
Node *left, *right;
// Helper function to count all subtrees having same value of nodes
// The function returns the value of the root node if all nodes in subtree
// rooted at root have same values, else it returns infinity
// Here count stores the result and it is passed by reference
int countSubtrees(Node* root, int &count)
// base case: empty tree
if (root == nullptr)
// if root is a leaf node, increase the count and return root node data
if (root->left == nullptr && root->right == nullptr)
// recurse for left subtree and right subtree
int left = countSubtrees(root->left, count);
int right = countSubtrees(root->right, count);
// 1. left subtree is empty & right subtree data matches with root
// 2. right subtree is empty & left subtree data matches with root
// 3. both left & right subtree are non-empty & their data matches with root
if ((left == INT_MIN && right == root->data) ||
(right == INT_MIN && left == root->data) ||
(left == right && left == root->data))
// increase the count and return root node data
// return infinity if root's data doesn't match with left or right subtree
// Main function to count all subtrees having same value of nodes
int countSubtrees(Node* root)
int count = 0;
The time complexity of above solution is O(n) and auxiliary space used by the program is O(1).
Thanks for reading.