# Count all subtrees having same value of nodes in a binary tree

Given a binary tree, count all subtrees in it such that every node in the subtree have same value.

For example, consider below tree

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 –

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

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 🙂

Subscribe
Notify of
Guest

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

Guest
anshul

You use LONG_MIN.

Guest
kishore

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