Count Univalue Subtrees

medium tree dfs recursion

Problem

Given the root of a binary tree, return the number of univalue subtrees — subtrees in which every node has the same value.

Inputroot = [5,1,5,5,5,null,5]

Output4

Three leaf 5s plus the right child 5 are univalue subtrees.

tree (level-order, use 'n' for null)

def count_unival_subtrees(root):
    count = 0
    def dfs(node):
        nonlocal count
        if not node: return True
        left = dfs(node.left)
        right = dfs(node.right)
        ok = left and right and             (not node.left or node.left.val == node.val) and             (not node.right or node.right.val == node.val)
        if ok: count += 1
        return ok
    dfs(root)
    return count

function countUnivalSubtrees(root) {
  let count = 0;
  function dfs(node) {
    if (!node) return true;
    const l = dfs(node.left), r = dfs(node.right);
    const ok = l && r &&
      (!node.left || node.left.val === node.val) &&
      (!node.right || node.right.val === node.val);
    if (ok) count++;
    return ok;
  }
  dfs(root);
  return count;
}

class Solution {
    int count = 0;
    public int countUnivalSubtrees(TreeNode root) { dfs(root); return count; }
    boolean dfs(TreeNode node) {
        if (node == null) return true;
        boolean l = dfs(node.left), r = dfs(node.right);
        boolean ok = l && r &&
            (node.left == null || node.left.val == node.val) &&
            (node.right == null || node.right.val == node.val);
        if (ok) count++;
        return ok;
    }
}

class Solution {
    int count = 0;
    bool dfs(TreeNode* n) {
        if (!n) return true;
        bool l = dfs(n->left), r = dfs(n->right);
        bool ok = l && r &&
            (!n->left || n->left->val == n->val) &&
            (!n->right || n->right->val == n->val);
        if (ok) count++;
        return ok;
    }
public:
    int countUnivalSubtrees(TreeNode* root) { dfs(root); return count; }
};

Explanation

A univalue subtree is a subtree where every single node holds the same value. We want to count how many such subtrees exist. The key insight is that this question can be answered from the bottom up.

We use a post-order DFS: visit the children first, then decide about the current node. A subtree rooted at node is univalue only if three things are all true — its left side is univalue, its right side is univalue, and any child that exists matches node.val.

The recursion dfs(node) returns true or false meaning "is the subtree under me uniform?". We combine the children's answers with the value checks into ok. Whenever ok is true we do count += 1, then return ok upward so the parent can use it.

Notice that an empty child counts as true (a missing branch never breaks uniformity), and a single leaf is always univalue by itself.

Example: [5,1,5,5,5,null,5]. The three leaf 5s each count, and the right child 5 (whose only child is also 5) counts too, giving 4. The top 5 fails because its left child is 1.

Time: O(n) Space: O(h)