Count the number of unival subtrees in a binary tree

Given a binary tree, we need to count the number of unival subtrees (all nodes have same value).

For example:

1.)

Untitled-1

 

In this, each node has same value thus its a unival tree. And total unival subtrees are 6 i.e.

 

2.) Another example

 

Untitled-6

 

Above binary tree is not a unival since all nodes don’t have equal values.

But there are 4 subtrees which are unival.

Untitled-5

 

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).

 

 

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s