# Day #8: Number Of Unival Trees Using Python

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

%[https://gist.github.com/nmreddy1911/d72d9a5aaf6eb1352329f91930aa51e6]

**Output**

    No. of unival subtrees= 5

# Visualiser

To understand the recursion behind this code, please click [here](http://pythontutor.com/visualize.html#code=class%20Node%3A%0A%20%20%20%20def%20__init__%28self,%20value,%20left%3DNone,%20right%3DNone%29%3A%0A%20%20%20%20%20%20%20%20self.val%20%3D%20value%0A%20%20%20%20%20%20%20%20self.left%20%3D%20left%0A%20%20%20%20%20%20%20%20self.right%20%3D%20right%0A%0A%0Adef%20countSubTree%28root,%20count%29%3A%0A%20%20%20%20if%20root%20is%20None%3A%0A%20%20%20%20%20%20%20%20return%20True%0A%20%20%20%20left%20%3D%20countSubTree%28root.left,%20count%29%0A%20%20%20%20right%20%3D%20countSubTree%28root.right,%20count%29%0A%20%20%20%20%23%20checking%20root%20value%20and%20children's%20values%0A%20%20%20%20if%20left%20%3D%3D%20False%20or%20right%20%3D%3D%20False%3A%0A%20%20%20%20%20%20%20%20return%20False%0A%20%20%20%20if%20root.left%20and%20root.val%20!%3D%20root.left.val%3A%0A%20%20%20%20%20%20%20%20return%20False%0A%20%20%20%20if%20root.right%20and%20root.val%20!%3D%20root.right.val%3A%0A%20%20%20%20%20%20%20%20return%20False%0A%20%20%20%20%23%20If%20all%20the%20above%20cases%20are%20not%20true,%20i.e.%20if%20the%20root%20value%20matches%20with%20both%20the%20children%0A%20%20%20%20%23%20then%20this%20case%20is%20reached,%20we%20increment%20the%20count%0A%20%20%20%20count%5B0%5D%20%2B%3D%201%0A%20%20%20%20return%20True%0A%0A%0Adef%20countTrees%28root%29%3A%0A%20%20%20%20count%20%3D%20%5B0%5D%0A%20%20%20%20%23%20calling%20a%20new%20function,%20to%20maintain%20the%20value%20of%20count%20in%20recursive%20calls%0A%20%20%20%20countSubTree%28root,%20count%29%0A%20%20%20%20return%20count%5B0%5D%0A%0A%0Aroot%20%3D%20Node%280,%20Node%281%29,%20Node%280,%20Node%281,%20Node%281%29,%20Node%281%29%29,%20Node%280%29%29%29%0Aprint%28%22No.%20of%20unival%20subtrees%3D%22,%20countTrees%28root%29%29&cumulative=false&curInstr=113&heapPrimitives=nevernest&mode=display&origin=opt-frontend.js&py=3&rawInputLstJSON=%5B%5D&textReferences=false)

Feel free to reach out for any query clearance.

**Thanks and cheers:)**