Count Univalue Subtrees

Medium · Graphs · Explanation and code example

Depth First Search Without Using The Global Variable

How it works

The previous solution uses a global or instance variable to track the count. We can avoid this by passing a mutable container (like an array or reference) through the recursion. This makes the function more self-contained and easier to test, while keeping the same logic.

Steps

Define a recursive DFS function that takes the current node and a count array (or reference) as parameters.
Base case: if the node is null, return true.
Recursively check the left and right subtrees, passing the count array.
If both subtrees are uni-value and the current node's value matches its children's values (when they exist):
- Increment count[0] and return true.
Otherwise, return false.
Create a count array initialized to 0, call DFS on the root, and return count[0].

Complexity

Time complexity: O(n)
Space complexity: O(n)

Where n is the number of nodes in the given binary tree

Things to watch for

Short-Circuit Evaluation Breaking the Count

Using short-circuit evaluation with and can skip processing one subtree entirely, causing missed counts. Both subtrees must be fully traversed to count all uni-value subtrees, even if one returns false.

Comparing Node Values Before Checking Null

Attempting to access a child's value without first checking if the child exists causes a null pointer exception. Always verify the child is not null before comparing values.

Incrementing Count for Non-Univalue Subtrees

A common mistake is incrementing the count before validating that the current node's value matches its children. The count should only increase after confirming all uni-value conditions are met.

Python code example

from typing import Optional

class Solution:
    def countUnivalSubtrees(self, root: Optional[TreeNode]) -> int:
        def dfs(node, count):
            if node is None:
                return True

            isLeftUniValue = dfs(node.left, count)
            isRightUniValue = dfs(node.right, count)

            # If both the children form uni-value subtrees, we compare the value of
            # chidrens node with the node value.
            if isLeftUniValue and isRightUniValue:
                if node.left and node.val != node.left.val:
                    return False
                if node.right and node.val != node.right.val:
                    return False

                count[0] += 1
                return True
            # Else if any of the child does not form a uni-value subtree, the subtree
            # rooted at node cannot be a uni-value subtree.
            return False

        count = [0]
        dfs(root, count)
        return count[0]

C++ code example

class Solution {
public:
    bool dfs(TreeNode* node, int& count) {
        if (node == nullptr) {
            return true;
        }

        bool isLeftUniValue = dfs(node->left, count);
        bool isRightUniValue = dfs(node->right, count);

        // If both the children form uni-value subtrees, we compare the value of
        // chidren's node with the node value.
        if (isLeftUniValue && isRightUniValue) {
            if (node->left != nullptr && node->left->val != node->val) {
                return false;
            }
            if (node->right != nullptr && node->right->val != node->val) {
                return false;
            }
            count++;
            return true;
        }
        // Else if any of the child does not form a uni-value subtree, the subtree
        // rooted at node cannot be a uni-value subtree.
        return false;
    }

    int countUnivalSubtrees(TreeNode* root) {
        int count = 0;
        dfs(root, count);
        return count;
    }
};

Source and license

Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.

Check the explanation on LeetCode

Your recall check is in progress. Write your attempt before revealing the explanation.

Resume recall check

Browse all problem explanations