Domain 2MediumCORE

Count Univalue Subtrees

We are given a binary tree (root) and need to count how many subtrees exist where every node within that subtree shares the exact same value as its root (and consequently all other nodes in it).

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Tree

250. Count Univalue Subtrees

Model: qwen3.5:9b
Topics: Tree
FAANG asked: 1
Acceptance rate: 53.5%


Problem Breakdown

We are given a binary tree (root) and need to count how many subtrees exist where every node within that subtree shares the exact same value as its root (and consequently all other nodes in it).

Inputs: A root of a binary tree (TreeNode). Outputs: An integer representing the total count. Key Definitions: A “subtree” is defined by any single node acting as its own root, including leaves and internal nodes. It does not mean just connected components; every node can be the start of a valid univalue subtree if conditions are met.

Edge Cases & Constraints:

  • Empty Tree (root is None): Should return 0 immediately.
  • Single Node: Always counts as 1 (a single node trivially satisfies “all nodes have same value”).
  • Mixed Values: A parent might match one child but not the other, breaking univalue status for that specific subtree root.
  • Negative/Zero Values: Handled naturally by integer comparison; no special logic needed beyond equality checks.

Intuition

If we were to solve this naively, we would iterate through every node in the tree and treat it as a potential root of an univalue subtree. For each candidate, we’d traverse its entire subtree to verify if all nodes match that value. This results in O(N2)O(N^2) time complexity because for each of the NN nodes, we might visit up to NN descendants. Given constraints allow N=1000N=1000, this is acceptable but not optimal; a strong candidate aims for linear time.

The key insight comes from realizing that whether a subtree rooted at node is univalue depends entirely on its children:

  1. Is the left child’s subtree valid? (If it exists, does it match?)
  2. Is the right child’s subtree valid?
  3. Do both children’s values equal the current node’s value?

This dependency suggests a Post-Order Traversal (Bottom-Up). We don’t need to know if node is univalue until we’ve verified its left and right branches are consistent with it. By returning information from recursive calls, we can build up the solution efficiently in O(N)O(N).

Approach

We will use a Depth-First Search (DFS) approach that returns two pieces of information implicitly:

  1. A boolean indicating if the current subtree is univalue.
  2. We maintain an external counter to accumulate valid subtrees found during traversal.

Algorithm Steps:

  1. Define a helper function dfs(node) inside the main solution scope.
  2. Base Case: If node is None, return True. An empty subtree technically satisfies the condition vacuously, allowing us to focus on value matching for actual nodes later.
  3. Recursive Step:
    • Call left = dfs(left_child). Check if left child exists and matches current node’s value (not left or left.val == root.val). Actually simpler logic: If a child is None, it doesn’t break the univalue property (it just contributes no nodes). So we check existence first.
    • Call right = dfs(right_child). Same logic for right side.
  4. Logic Check: The current subtree rooted at node is valid if (left_subtree_valid) AND (right_subtree_valid) AND ((not left or node.val == left.val)).
  5. If the check passes, increment our global counter and return True. Otherwise, return False.
  6. Handle empty root input before starting recursion to avoid confusion with base cases inside DFS (though standard logic handles it if we treat None as valid child state).

Complexity Analysis

  • Time: O(N)O(N) where N is the number of nodes in the tree. We visit each node exactly once during the post-order traversal. All operations per node are constant time comparisons and assignments.
  • Space: O(H)O(H) for recursion stack space, where H is the height of the tree. In a balanced tree this is O(log⁡N)O(\log N); in a skewed (linked-list-like) tree it degrades to O(N)O(N).

Solution

# 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

def countUnivalSubtrees(root: 'TreeNode') -> int:
    if not root:
        return 0
    
    # We use a list to hold the count so it can be modified in nested scope 
    # (or nonlocal keyword). Using [0] is idiomatic for mutable state.
    ans = [0] 
    
    def dfs(node):
        # Base case: empty subtree satisfies condition vacuously
        if not node:
            return True
        
        left_valid, right_valid = False, False
        
        # Recursive calls to children first (Post-order)
        if node.left:
            left_valid = dfs(node.left) and node.val == node.left.val
        else:
            left_valid = True
            
        if node.right:
            right_valid = dfs(node.right) and node.val == node.right.val
        else:
            right_valid = True
        
        # Check value consistency with children only if they exist
        is_left_match = (not node.left or node.val == node.left.val) and left_valid
        is_right_match = (not node.right or node.val == node.right.val) and right_valid
        
        current_is_unival = is_left_match and is_right_match
        
        if current_is_unival:
            ans[0] += 1
            
        return current_is_unival

    dfs(root)
    
    return ans[0]

Edge Cases Handled

  • Empty Tree (root is None): The initial check returns 0 immediately. If we passed it to DFS, the base case handles None nodes returning True without incrementing count (since no node exists).
  • Single Node: Left and Right are None. Logic sets both match flags to True. Current becomes unival. Count increments by 1. Returns True.
  • Mixed Values in Lineage: If a parent has value 5 but left child is valid subtree of value 3, the check (node.val == node.left.val) fails, preventing count increment for that specific root and returning False up the chain to prevent invalid propagation.