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

Binary Tree

There are 6 subtrees having same data

Binary Tree Count
 

 
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 –
 

Download   Run Complete Code

 
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

avatar
  Subscribe  
newest oldest most voted
Notify of
sid
Guest

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

anshul
Guest
anshul

You use LONG_MIN.

kishore
Guest
kishore

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