LeetCode 250 - Count Univalue Subtrees

Difficulty: 🟡 Medium
Topics: Tree, Depth-First Search, Binary Tree

Solution

Problem Understanding

The problem asks us to count how many subtrees in a binary tree are "uni-value" subtrees. A uni-value subtree is a subtree in which every node has the same value.

A subtree consists of a node together with all of its descendants. This means every node in the tree can potentially serve as the root of a subtree. Our task is to examine all such subtrees and determine how many satisfy the uni-value property.

The input is the root of a binary tree. Each node contains:

An integer value
A pointer to a left child
A pointer to a right child

The output is a single integer representing the number of uni-value subtrees.

Consider the first example:

The four uni-value subtrees are:

The left leaf node with value 5
The middle leaf node with value 5
The right leaf node with value 5
The subtree rooted at the right child 5

The subtree rooted at 1 is not uni-value because its children have different values. The entire tree is also not uni-value.

The constraints tell us:

The tree contains at most 1000 nodes
Node values range from -1000 to 1000

A tree of size 1000 is relatively small, but inefficient repeated subtree traversals can still lead to quadratic complexity. This suggests we should aim for an O(n) solution if possible.

Important edge cases include:

An empty tree
A tree with only one node
Trees where every node has the same value
Trees where no internal subtree is uni-value
Skewed trees that resemble linked lists

These cases can expose incorrect assumptions about recursion, null handling, or subtree validation.

Approaches

Brute Force Approach

A straightforward solution is to examine every subtree independently.

For each node:

Treat that node as the root of a subtree
Traverse the entire subtree
Check whether all nodes inside it share the same value
If yes, increment the answer

To validate a subtree, we recursively compare every descendant node against the root value.

This approach is correct because every subtree is explicitly checked. However, it performs redundant work. The same nodes are traversed repeatedly when validating overlapping subtrees.

For example, in a skewed tree with n nodes:

The root subtree checks n nodes
The next subtree checks n - 1 nodes
And so on

This leads to:

n + (n - 1) + (n - 2) + ... + 1 = O(n²)

Although the constraints are moderate, we can do better.

Optimal Approach

The key observation is that whether a subtree is uni-value depends entirely on its children.

A subtree rooted at node X is uni-value if:

Its left subtree is uni-value
Its right subtree is uni-value
The left child, if it exists, has the same value as X
The right child, if it exists, has the same value as X

This naturally suggests a postorder traversal:

First determine whether the left subtree is uni-value
Then determine whether the right subtree is uni-value
Finally determine whether the current subtree is uni-value

By computing this information bottom-up, each node is processed exactly once.

This eliminates redundant subtree traversals and gives an O(n) solution.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(h)	Repeatedly validates overlapping subtrees
Optimal	O(n)	O(h)	Single DFS traversal with bottom-up validation

Here, h represents the height of the tree.

Algorithm Walkthrough

Create a counter to store the number of uni-value subtrees.
Define a recursive DFS function that returns whether the subtree rooted at the current node is uni-value.
If the current node is None, return True.

An empty subtree is considered uni-value because it does not violate the condition. 4. Recursively check the left subtree. 5. Recursively check the right subtree. 6. If either subtree is not uni-value, return False.

Since the current subtree depends on both children being valid, failure in either child immediately disqualifies the current subtree. 7. If the left child exists and its value differs from the current node's value, return False. 8. If the right child exists and its value differs from the current node's value, return False. 9. If all checks pass:

Increment the global counter
Return True

After DFS completes, return the counter.

Why it works

The algorithm works because it processes the tree bottom-up. Every node determines whether its subtree is uni-value using already-computed information from its children.

A subtree can only be uni-value if both child subtrees are themselves uni-value and all child values match the current node's value. Since these conditions are both necessary and sufficient, every subtree is classified correctly exactly once.

Python Solution

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

from typing import Optional

class Solution:
    def countUnivalSubtrees(self, root: Optional[TreeNode]) -> int:
        count = 0

        def dfs(node: Optional[TreeNode]) -> bool:
            nonlocal count

            if node is None:
                return True

            left_is_unival = dfs(node.left)
            right_is_unival = dfs(node.right)

            if not left_is_unival or not right_is_unival:
                return False

            if node.left and node.left.val != node.val:
                return False

            if node.right and node.right.val != node.val:
                return False

            count += 1
            return True

        dfs(root)
        return count

The implementation uses a nested DFS helper function that returns a boolean indicating whether the current subtree is uni-value.

The base case handles None nodes by returning True. This simplifies the logic because missing children do not invalidate a subtree.

The recursive calls evaluate the left and right subtrees first. This is a postorder traversal because the current node depends on information from its descendants.

After both recursive calls return, the function checks:

Whether both child subtrees are uni-value
Whether the child values match the current node value

If any condition fails, the subtree is not uni-value.

Otherwise, the subtree qualifies, so the counter is incremented and True is returned.

The nonlocal keyword allows the nested DFS function to update the shared counter variable.

Go Solution

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func countUnivalSubtrees(root *TreeNode) int {
    count := 0

    var dfs func(node *TreeNode) bool

    dfs = func(node *TreeNode) bool {
        if node == nil {
            return true
        }

        leftIsUnival := dfs(node.Left)
        rightIsUnival := dfs(node.Right)

        if !leftIsUnival || !rightIsUnival {
            return false
        }

        if node.Left != nil && node.Left.Val != node.Val {
            return false
        }

        if node.Right != nil && node.Right.Val != node.Val {
            return false
        }

        count++
        return true
    }

    dfs(root)
    return count
}

The Go implementation follows the same recursive structure as the Python solution.

The main difference is that Go uses explicit pointer checks with nil instead of Python's truthiness checks. The recursive helper is declared as a function variable because Go requires recursive anonymous functions to be defined before assignment.

Integer overflow is not a concern because the maximum number of nodes is only 1000.

Worked Examples

Example 1

Input: [5,1,5,5,5,null,5]

Tree:

Traversal order is postorder.

Current Node	Left Uni-value	Right Uni-value	Valid?	Count
Left leaf 5	True	True	Yes	1
Middle leaf 5	True	True	Yes	2
Node 1	True	True	No, children differ	2
Right leaf 5	True	True	Yes	3
Right subtree 5	True	True	Yes	4
Root 5	False	True	No	4

Final answer:

Example 2

Input: []

The tree is empty.

The DFS immediately returns without incrementing the counter.

Step	Action	Count
Root is None	Return True	0

Final answer:

Example 3

Input: [5,5,5,5,5,null,5]

Tree:

Every subtree satisfies the uni-value condition.

Current Node	Valid?	Count
Left leaf 5	Yes	1
Middle leaf 5	Yes	2
Left subtree 5	Yes	3
Right leaf 5	Yes	4
Right subtree 5	Yes	5
Root 5	Yes	6

Final answer:

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each node is visited exactly once
Space	O(h)	Recursion stack depth equals tree height

The algorithm performs a single DFS traversal of the tree. Each node does constant work after processing its children, so total time is linear in the number of nodes.

The space complexity comes from recursive call stack usage. In a balanced tree, the height is O(log n). In the worst case of a skewed tree, the height becomes O(n).

Test Cases

# Definition for testing
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def countUnivalSubtrees(self, root):
        count = 0

        def dfs(node):
            nonlocal count

            if node is None:
                return True

            left_is_unival = dfs(node.left)
            right_is_unival = dfs(node.right)

            if not left_is_unival or not right_is_unival:
                return False

            if node.left and node.left.val != node.val:
                return False

            if node.right and node.right.val != node.val:
                return False

            count += 1
            return True

        dfs(root)
        return count

sol = Solution()

# Example 1
root1 = TreeNode(5)
root1.left = TreeNode(1)
root1.right = TreeNode(5)
root1.left.left = TreeNode(5)
root1.left.right = TreeNode(5)
root1.right.right = TreeNode(5)

assert sol.countUnivalSubtrees(root1) == 4  # mixed valid and invalid subtrees

# Example 2
assert sol.countUnivalSubtrees(None) == 0  # empty tree

# Example 3
root3 = TreeNode(5)
root3.left = TreeNode(5)
root3.right = TreeNode(5)
root3.left.left = TreeNode(5)
root3.left.right = TreeNode(5)
root3.right.right = TreeNode(5)

assert sol.countUnivalSubtrees(root3) == 6  # all subtrees valid

# Single node
root4 = TreeNode(7)

assert sol.countUnivalSubtrees(root4) == 1  # single node is always uni-value

# Root invalid, children valid
root5 = TreeNode(1)
root5.left = TreeNode(1)
root5.right = TreeNode(2)

assert sol.countUnivalSubtrees(root5) == 2  # only leaves qualify

# Skewed tree with same values
root6 = TreeNode(3)
root6.right = TreeNode(3)
root6.right.right = TreeNode(3)

assert sol.countUnivalSubtrees(root6) == 3  # every subtree valid

# Skewed tree with differing values
root7 = TreeNode(1)
root7.right = TreeNode(1)
root7.right.right = TreeNode(2)

assert sol.countUnivalSubtrees(root7) == 1  # only last leaf valid

# Negative values
root8 = TreeNode(-1)
root8.left = TreeNode(-1)
root8.right = TreeNode(-1)

assert sol.countUnivalSubtrees(root8) == 3  # negative values handled correctly

Test	Why
`[5,1,5,5,5,null,5]`	Standard mixed-case example
`[]`	Empty tree boundary case
`[5,5,5,5,5,null,5]`	Entire tree is uni-value
Single node tree	Smallest non-empty input
Root differs from one child	Ensures invalid parent detection
Skewed identical tree	Tests recursion depth and chaining
Skewed differing tree	Ensures partial validity handling
Negative values	Confirms value range handling

Edge Cases

Empty Tree

An empty tree contains no subtrees, so the correct answer is 0.

This case can cause bugs if the implementation assumes the root always exists. The solution handles this naturally because the DFS immediately returns True for None, while the counter remains zero.

Single Node Tree

A single node is always a uni-value subtree because there are no differing descendants.

Some implementations incorrectly require both children to exist before validating a subtree. This solution avoids that issue by treating missing children as valid.

Parent Matches One Child but Not the Other

Consider:

    1
   / \
  1   2

The leaf nodes are valid uni-value subtrees, but the root subtree is not.

A common mistake is checking only whether child subtrees are valid without comparing child values to the parent value. The implementation explicitly checks both child values before counting the current subtree.

Skewed Trees

A tree shaped like a linked list can expose recursion issues or incorrect assumptions about balanced structure.

For example:

Every subtree should count correctly. Since the algorithm only depends on recursive subtree validity and local comparisons, it works correctly regardless of tree shape.