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 (
rootisNone): 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 time complexity because for each of the nodes, we might visit up to descendants. Given constraints allow , 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:
- Is the left child’s subtree valid? (If it exists, does it match?)
- Is the right child’s subtree valid?
- 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 .
Approach
We will use a Depth-First Search (DFS) approach that returns two pieces of information implicitly:
- A boolean indicating if the current subtree is univalue.
- We maintain an external counter to accumulate valid subtrees found during traversal.
Algorithm Steps:
- Define a helper function
dfs(node)inside the main solution scope. - Base Case: If
nodeisNone, returnTrue. An empty subtree technically satisfies the condition vacuously, allowing us to focus on value matching for actual nodes later. - 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.
- Call
- Logic Check: The current subtree rooted at
nodeis valid if (left_subtree_valid) AND (right_subtree_valid) AND ((not left or node.val == left.val)). - If the check passes, increment our global counter and return
True. Otherwise, returnFalse. - 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: 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: for recursion stack space, where H is the height of the tree. In a balanced tree this is ; in a skewed (linked-list-like) tree it degrades to .
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 (
rootisNone): 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
5but left child is valid subtree of value3, 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.