Follow

# .css-ecb9sr{display:-webkit-box;display:-webkit-flex;display:-ms-flexbox;display:flex;-webkit-flex-direction:row;-ms-flex-direction:row;flex-direction:row;-webkit-align-items:center;-webkit-box-align:center;-ms-flex-align:center;align-items:center;width:16rem;} Follow # Day #8: Number Of Unival Trees Using Python

Manish Reddy Nandineni
·Jun 19, 2020·

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
``````