Hello everyone. Today is the Day 8 of the #100DaysOfCodeChallenge. Received a problem previously asked by Google with an easy tag to it.
The Question On Day #8:
A unival tree (which stands for "universal value") is a tree where all nodes under it have the same value.
Given the root to a binary tree, count the number of unival subtrees.
For example, the following tree has 5 unival subtrees:
0
/ \
1 0
/ \
1 0
/ \
1 1
Approach
- Before moving on to the main logic, let's discuss about the Brute Force way to solve this:
- Starting from the root, we check if the immediate children have the same value as the root node, and then the children of the immediate nodes and so on.
- We repeat this process for every subtree ending up in time taking process.
Optimal Way
- The optimal way to solve this problem is by using the bottom-up approach. We first start from the leaf nodes, and move to the upper levels and use the unary value of the child subtree to decide if the main tree is a unary tree or not.
Python Code
Output
No. of unival subtrees= 5
Visualiser
To understand the recursion behind this code, please click here
Feel free to reach out for any query clearance.
Thanks and cheers:)