Count Univalue Subtrees

Master this topic with zero to advance depth.

Count Univalue Subtrees

Count same val subtrees.

Hard

Approach 1

Level I: Brute Force (Check each node)

Intuition

A uni-value subtree is a subtree where all nodes have the same value. A brute force approach checks for every node n if all nodes in its subtree have the same value as n.val.

Thought Process

Define isUnival(node, val) helper.
In main count function:
- If isUnival(root, root.val), increment count.
- Recurse to children.

⏱ O(N^2)💾 O(H)

Detailed Dry Run

Node	Subtree Values	All Same?	Action
1	[1, 1, 1]	YES	count++
5	[5, 5]	YES	count++

java

public class Main {
    int count = 0;
    public int countUnivalSubtrees(TreeNode root) {
        if (root == null) return 0;
        if (isUnival(root, root.val)) count++;
        countUnivalSubtrees(root.left);
        countUnivalSubtrees(root.right);
        return count;
    }
    private boolean isUnival(TreeNode node, int val) {
        if (node == null) return true;
        return node.val == val && isUnival(node.left, val) && isUnival(node.right, val);
    }
}

Approach 2

Level II: Recursive DFS (Parent Passing)

Intuition

Instead of checking every node as root, we can pass the parent's value down. If a node and its children all match that value, we have a candidate. This approach is slightly more efficient than checking every node but still redundant compared to bottom-up.

Logic

For each node, check if it's the root of a unival subtree by matching it with its own value using an isUnival(node, target) helper.

⏱ O(N^2)💾 O(H)

Detailed Dry Run

Node 5. isUnival(5, 5) -> returns true if all in 5's subtree are 5.

java

public class Main {
    int count = 0;
    public int countUnivalSubtrees(TreeNode root) {
        dfs(root);
        return count;
    }
    private void dfs(TreeNode node) {
        if (node == null) return;
        if (isUnival(node, node.val)) count++;
        dfs(node.left); dfs(node.right);
    }
    private boolean isUnival(TreeNode node, int target) {
        if (node == null) return true;
        if (node.val != target) return false;
        return isUnival(node.left, target) && isUnival(node.right, target);
    }
}

Approach 3

Level III: Optimal (Bottom-Up DFS)

Intuition

Thought Process

Instead of re-checking each subtree, we can use a bottom-up approach. A node is the root of a uni-value subtree if children are uni-value and match the parent's value.

Patterns

DFS Result Aggregation: Pass child status up to parents.

Complexity

Time: $O(N)$
Space: $O(H)$

⏱ O(N)💾 O(H)

Detailed Dry Run

Node	Left Uni?	Right Uni?	Matches Children?	Count
Leaf	true	true	yes	count++
Root	true	true	yes	count++

java

public class Main {
    int count = 0;
    public int countUnivalSubtrees(TreeNode root) {
        isUnival(root);
        return count;
    }
    private boolean isUnival(TreeNode node) {
        if (node == null) return true;
        boolean left = isUnival(node.left);
        boolean right = isUnival(node.right);
        if (left && right) {
            if (node.left != null && node.val != node.left.val) return false;
            if (node.right != null && node.val != node.right.val) return false;
            count++;
            return true;
        }
        return false;
    }
}

⚠️ Common Pitfalls & Tips

You must call DFS for both children before returning, even if one child is not a uni-value subtree. This is because the other child might still contain uni-value subtrees that need to be counted.

← Previous QuestionRecover Binary Search Tree

Next Question →Serialize and Deserialize N-ary Tree

Found an issue or have a suggestion?

Help us improve! Report bugs or suggest new features on our Telegram group.