Course4all

Count Univalue Subtrees

Expert Answer & Key Takeaways

A complete guide to understanding and implementing Trees.

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

  1. Define isUnival(node, val) helper.
  2. In main count function:
    • If isUnival(root, root.val), increment count.
    • Recurse to children.
⏱ O(N^2)💾 O(H)

Detailed Dry Run

NodeSubtree ValuesAll Same?Action
1[1, 1, 1]YEScount++
5[5, 5]YEScount++
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)O(N)
  • Space: O(H)O(H)
⏱ O(N)💾 O(H)

Detailed Dry Run

NodeLeft Uni?Right Uni?Matches Children?Count
Leaftruetrueyescount++
Roottruetrueyescount++
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.

Course4All Technical Board

Verified Expert

Senior Software Engineers & Algorithmic Experts

Our DSA content is authored and reviewed by engineers from top tech firms to ensure optimal time and space complexity analysis.

Pattern: 2026 Ready
Updated: Weekly
← Previous QuestionRecover Binary Search Tree
Next Question →Serialize and Deserialize N-ary Tree