## Similar Problems

Similar Problems not available

# Count Univalue Subtrees - Leetcode Solution

## Companies:

LeetCode: Count Univalue Subtrees Leetcode Solution

Difficulty: Medium

Topics: tree binary-tree depth-first-search

Problem description: Given a binary tree, count the number of uni-value subtrees. A uni-value subtree means all nodes of the subtree have the same value.

Example:

Input: root = [5,1,5,5,5,null,5]

```
5
/ \
1 5
/ \ \
5 5 5
```

Output: 4

Solution: To solve this problem, we need to solve it recursively. At each node, we will check if its left and right children are uni-valued subtrees or not. If they are, we will check if the value of the current node is equal to the value of its children. If yes, then we can say that the current node is also a uni-valued subtree. Otherwise, it's not. We will return this info to the parent node.

We will use a variable count to keep track of the number of uni-valued subtrees. Initially, we set it to 0. At each node, if it's a uni-valued subtree, we increment count by 1.

The base case for recursion is when the current node is null. In that case, we return true, meaning it's a uni-valued subtree.

Here's the Python code:

def countUnivalSubtrees(self, root: Optional[TreeNode]) -> int: self.count = 0

```
def isUnival(node):
if node is None:
return True
left = isUnival(node.left)
right = isUnival(node.right)
if left and right:
if node.left and node.left.val != node.val:
return False
if node.right and node.right.val != node.val:
return False
self.count += 1 # current node is also a uni-valued subtree
return True
return False
isUnival(root) # call the recursive function
return self.count
```

Time Complexity: O(n). Since we are visiting each node of the binary tree only once, the time complexity is O(n).

Space Complexity: O(h). The space used by the recursion stack is equal to the height of the binary tree, which is at most O(n) for a skewed tree and O(log n) for a balanced tree.

## Count Univalue Subtrees Solution Code

`1`