(Daily Coding Problem: February 23rd, 2020)Given the root of a binary tree, count the number of unival subtrees.

Hey Guys, Recently I came across the daily coding problem. I really liked the idea behind solving every day one question of data structure. Being a full-time developer for 2.5 years, this seemed to be a very intuitive and catchy approach for getting a grip on data structures. I will be sharing my solutions to the everyday problem and would love to have a hearty discussion on it.

Question:- Given the root of a binary tree, count the number of unival subtrees.

A unival tree (which stands for “universal value”) is a tree where all nodes under it have the same value.

Image by https://www.shadabahmed.com/

Solution:-

When it comes to the binary tree, I immediately start looking for a recursive solution.

Hence, I first wanted to make the end/base case:

In this scenario, I found 2 base cases:-

1. When the node is null, the answer, in that case, is the no of unival tree is 0.
   But at the same time, it will not affect the parent node’s ability to be a unival tree. Hence, I marked isUnival as true(exception — even though it's not a unival tree, I marked it as true because we are maintaining this only for computing parent node’s isUnival tree feature) and count as 0.
2. When the node’s left and right nodes are null, in that case, is the no of unival tree is 1.
   Hence, I marked isUnival as true and count as 1.

Now to traverse back, I take a look on both left and right child’s node isUnival flag value and only if they are both unival, the current node can be unival.

Ofcourse, we have to compare the immediate children nodes value to the current node value to deduce whether the current node is unival or not.

Note:- We do not have to traverse down till the leaf nodes of the subtree(where the current node is root) because while traversing back we are setting the value of isUnival as true/false which tells us whether the values in the subtree of the current node are same or not).

Node.value has to be equal to node.left.value (if node.left present) and node.right.value (if node.right.present) along with its child nodes have to pass the criteria of univalTree for the current node to be unival.

Below is the code implementation in java for the problem based on my approach -

Time Complexity:- O(n)

That’s all from my side, thank you so much for reading the blog. I will be continuing this series and will keep on discussing everyday problems. For any further discussions, please feel free to reach out to me at divyabiyani26@gmail.com.