Given a binary tree, we need to count the number of unival subtrees (all nodes have same value).
For example:
1.)
In this, each node has same value thus its a unival tree. And total unival subtrees are 6 i.e.
2.) Another example
Above binary tree is not a unival since all nodes don’t have equal values.
But there are 4 subtrees which are unival.
From above explanation it is clear that leaf nodes are always unival trees.
Method 1 (Brute Force)
First we make a function that checks whether a binary tree rooted with a given node is unival or not. This function takes a linear time to execute since we will check each node that they all have equal values and their left and right subtrees are also univals.
Now, to count the number of subtrees, we execute above function on each node of binary tree and count the subtrees accordingly. This would lead to O(n^2) time complexity.
Click here to see the C++ implementation.
Method 2 (Linear Time)
In above approach, we are doing a top to down traversal and doing a check on each node. In this approach we will go from down to up and use our previous result to calculate next result. In this way recalculation for subtrees is avoided.
Click here to see the C++ implementation.
Time complexity: O(n).
CodeBook 