LeetCode Solutions Blog

Count Univalue Subtrees

Number: 250

Difficulty: Medium

Paid? Yes

Problem Description

Given the root of a binary tree, count the number of univalue subtrees. A univalue subtree is one in which all the nodes have the same value. An empty tree is not considered as a subtree.

Key Insights

Perform a postorder traversal (left, right, root) to determine whether each subtree is univalue.
Treat null nodes as univalue to ease the recursion.
A node's subtree is univalue if both left and right subtrees are univalue and, if they exist, their values equal the current node’s value.
Use a global or external counter that increments every time a univalue subtree is confirmed.

Space and Time Complexity

Time Complexity: O(n), where n is the number of nodes, since each node is visited once. Space Complexity: O(h), where h is the height of the tree, due to the recursion stack.

Solution

We use a recursive DFS approach (postorder traversal) to solve the problem. For each node, we recursively check its left and right subtrees to decide if they are univalue. By default, if a child is null, it is considered univalue. Then, we verify the current node’s value against its non-null children. If both conditions hold (subtrees are univalue and matching values), we count the current node's subtree as univalue. This DFS checks in a bottom-up manner, ensuring that the properties required for a subtree to be univalue are maintained. The key trick is to return a boolean indicating if the subtree at each node is univalue and, while backtracking, increment the counter appropriately.

Code Solutions

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def countUnivalSubtrees(self, root: TreeNode) -> int:
        # Initialize count
        self.count = 0

        # Helper function performs postorder DFS
        def isUnival(node):
            # Base case, null nodes are considered univalue
            if node is None:
                return True
            
            # Recursive calls for left and right subtrees
            leftUnival = isUnival(node.left)
            rightUnival = isUnival(node.right)

            # Check if left child exists and its value does not match current node's value
            if node.left and node.left.val != node.val:
                leftUnival = False
            # Check if right child exists and its value does not match current node's value
            if node.right and node.right.val != node.val:
                rightUnival = False
            
            # If either left or right subtree is not univalue, then the current subtree is not univalue
            if leftUnival and rightUnival:
                # Increment the count if the subtree rooted at the current node is univalue
                self.count += 1
                return True
            else:
                return False

        # Start recursion from root
        isUnival(root)
        return self.count

# Example usage:
# Construct the binary tree: [5,1,5,5,5,null,5]
# root = TreeNode(5)
# root.left = TreeNode(1, TreeNode(5), TreeNode(5))
# root.right = TreeNode(5, None, TreeNode(5))
# print(Solution().countUnivalSubtrees(root))  # Output: 4