Watch 10 video solutions for Count Univalue Subtrees, a medium level problem involving Tree, Depth-First Search, Binary Tree. This walkthrough by NeetCode has 196,060 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Given the root of a binary tree, return the number of uni-value subtrees.
A uni-value subtree means all nodes of the subtree have the same value.
Example 1:
Input: root = [5,1,5,5,5,null,5] Output: 4
Example 2:
Input: root = [] Output: 0
Example 3:
Input: root = [5,5,5,5,5,null,5] Output: 6
Constraints:
[0, 1000].-1000 <= Node.val <= 1000Problem Overview: Given a binary tree, count how many subtrees are univalue. A subtree is univalue if every node inside it has the same value. Each node can be the root of its own subtree, so you must verify whether all nodes below it match.
Approach 1: Brute Force Subtree Validation (O(n^2) time, O(h) space)
Traverse every node and treat it as the root of a potential univalue subtree. For each node, run a helper DFS that checks whether all nodes in that subtree match the root value. This repeatedly scans the same nodes when validating overlapping subtrees, which leads to O(n^2) time in the worst case for skewed trees. Space complexity is O(h) due to recursion depth, where h is the tree height. This approach is straightforward but inefficient because subtree validation is recomputed many times.
Approach 2: Postorder DFS with State Propagation (O(n) time, O(h) space)
Traverse the tree using postorder DFS so children are processed before their parent. Each recursive call returns whether the current subtree is univalue. A node forms a univalue subtree if its left and right subtrees are univalue and their values (if they exist) match the current node's value. When this condition holds, increment a global counter and return true to the parent. Every node is visited exactly once, giving O(n) time complexity with O(h) recursion stack space. This approach avoids repeated subtree scans by propagating validity information upward.
The algorithm relies on standard traversal patterns from depth-first search applied to a binary tree. Postorder traversal is key because a node's validity depends on the results from both children.
Recommended for interviews: The postorder DFS approach is what interviewers expect. It demonstrates that you can propagate state during recursion and avoid redundant work. Mentioning the brute force method first shows understanding of the problem space, but implementing the O(n) DFS solution proves stronger algorithmic thinking when working with tree structures.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Subtree Validation | O(n^2) | O(h) | Conceptual starting point to understand subtree validation logic |
| Postorder DFS with State Propagation | O(n) | O(h) | Optimal solution for interviews and production tree traversal problems |