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(n^{2}).

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 –**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 |
// Data structure to store a Binary Tree node struct Node { int data; 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) return INT_MIN; // if root is a leaf node, increase the count and return root node data if (root->left == nullptr && root->right == nullptr) { count++; return root->data; } // 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 count++; return root->data; } // return infinity if root's data doesn't match with left or right subtree return INT_MAX; } // Main function to count all subtrees having same value of nodes int countSubtrees(Node* root) { int count = 0; countSubtrees(root, count); return count; } |

The time complexity of above solution is O(n) and auxiliary space used by the program is O(1).

**Thanks for reading.**

Please use ideone or C++ Shell or any other online compiler link to post code in comments.

Like us? Please spread the word and help us grow. Happy coding 🙂

## Leave a Reply

can this be done without using INT_MIN.. what if the node’s data is INT_MIN

You use LONG_MIN.

I Can’t understand the example, how is 7 a part of the subtree having same data..?

Thanks for sharing your concerns. Note that a tree with only one node is still a tree and will be considered as tree with same data in all its nodes. Hope you’re clear now.

Thanks.. understood.