LeetCode 250: Count Univalue Subtrees Solution in Python – A Step-by-Step Guide

Imagine walking through a tree where some branches and their leaves all share the same value—like a cluster of "5"s hanging together. That’s the heart of LeetCode 250: Count Univalue Subtrees! This medium-level problem asks you to count how many subtrees in a binary tree have all nodes with the same value. Using Python, we’ll explore two solutions: the Best Solution, a bottom-up DFS with validation, and an Alternative Solution, a top-down DFS with subtree checking. With detailed examples, clear code, and beginner-friendly breakdowns—especially for the best solution—this guide will help you master tree traversal and boost your coding skills. Let’s count those uniform subtrees!

What Is LeetCode 250: Count Univalue Subtrees?

In LeetCode 250: Count Univalue Subtrees, you’re given a binary tree, and your task is to count the number of "univalue subtrees"—subtrees where every node has the same value. This problem builds on tree concepts from challenges like LeetCode 236: Lowest Common Ancestor of a Binary Tree, but focuses on value consistency rather than structural properties.

Problem Statement

Input: A binary tree root node.
Output: An integer—the count of univalue subtrees.
Rules: A univalue subtree has all nodes with the same value; a single node is a valid subtree.

Constraints

Tree nodes: 0 to 2000.
Node values: -1000 to 1000.

Examples

Input: Tree with root = 5, left = 1 (left = 5, right = 5), right = 5

Text representation:

Root: 5
Left: 1

Left: 5
Right: 5

Right: 5

Output: 4 (subtrees: 5 (left-left), 5 (left-right), 5 (right), 5 (root-right)).

Input: Tree with root = 5, left = 5, right = 5

Text representation:

Root: 5
Left: 5
Right: 5

Output: 3 (subtrees: 5 (left), 5 (right), 5 (whole tree)).

Understanding the Problem: Counting Uniform Subtrees

To solve LeetCode 250: Count Univalue Subtrees in Python, we need to identify and count every subtree where all nodes share the same value. A subtree includes a node and all its descendants (or just the node itself). A naive approach—checking every possible subtree—would be too slow. Instead, we’ll use two methods: 1. Best Solution (Bottom-Up DFS): O(n) time—fast and efficient. 2. Alternative Solution (Top-Down DFS): O(n * h) time—simpler but less optimal.

Let’s dive into the best solution with extra detail for beginners.

Best Solution: Bottom-Up DFS with Validation

Why This Is the Best Solution

The bottom-up DFS approach is the top choice for LeetCode 250 because it traverses the tree once in O(n) time, checking each subtree’s univalue property as it builds up from leaves to root. It uses a clever validation trick to count subtrees efficiently, making it both fast and beginner-friendly once understood.

How It Works

Picture this solution as climbing a tree from the bottom up, checking each branch to see if all its leaves and twigs match. You start at the leaves, confirm they’re univalue, and then ask each parent, “Do you and your kids all agree?” Here’s how it works, explained simply:

Bottom-Up Idea: Start at the leaves and work up. A leaf is univalue by itself (one node). For a parent, it’s univalue if its value matches its left and right subtrees, and those subtrees are univalue too.
DFS Process:

Visit each node starting from the bottom (post-order: left, right, root).
For each node, check if it forms a univalue subtree with its children.
Use a helper function to return whether a subtree is univalue and its value.

Counting: Keep a running total of univalue subtrees, adding 1 whenever a node and its subtree pass the test.
Validation: If a subtree isn’t univalue, pass that info up so parents know not to count it.

It’s like inspecting a family tree—everyone in a group must share the same “name” (value)!

Step-by-Step Example

Example: Tree with root = 5, left = 1 (left = 5, right = 5), right = 5

Text Representation:

Root: 5
Left: 1

Left: 5
Right: 5

Right: 5

DFS Traversal:

Left-Left (5): Leaf, univalue = true, value = 5, count +1 → 1.
Left-Right (5): Leaf, univalue = true, value = 5, count +1 → 2.
Left (1):

Left child: univalue, value 5.
Right child: univalue, value 5.
Root 1 ≠ 5, not univalue, count unchanged → 2.

Right (5): Leaf, univalue = true, value = 5, count +1 → 3.
Root (5):

Left child: not univalue.
Right child: univalue, value 5.
Root 5 matches right 5, but left fails, not univalue for whole tree.
Right subtree already counted, so count unchanged → 3.
But root-right (5-5) is univalue, count +1 → 4.

Result: 4.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained for beginners:

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: TreeNode) -> int:
        # Step 1: Set up our counter
        self.count = 0

        # Step 2: Helper function to check univalue
        def dfs(node):
            if not node:
                return True, None  # Empty is univalue (base case)

            # Step 3: Check left and right subtrees
            left_univalue, left_val = dfs(node.left)
            right_univalue, right_val = dfs(node.right)

            # Step 4: Leaf case
            if not node.left and not node.right:
                self.count += 1  # Leaf is univalue
                return True, node.val

            # Step 5: Check if current node forms univalue subtree
            current_val = node.val
            is_univalue = True

            # Compare with left
            if node.left and (not left_univalue or left_val != current_val):
                is_univalue = False
            # Compare with right
            if node.right and (not right_univalue or right_val != current_val):
                is_univalue = False

            # Step 6: If univalue, increment count
            if is_univalue:
                self.count += 1

            # Step 7: Return status for parent
            return is_univalue, current_val

        # Step 8: Start DFS
        dfs(root)
        return self.count

Time Complexity: O(n)—visits each node once.
Space Complexity: O(h)—recursion stack, where h is tree height.

This solution is like a tree inspector climbing up, counting matching groups—super efficient!

Alternative Solution: Top-Down DFS with Subtree Checking

Why an Alternative Approach?

The top-down DFS approach starts at the root and checks each subtree by exploring downward, counting univalue subtrees as it goes. It’s less efficient but easier to visualize for beginners who like seeing the whole tree first.

How It Works

Start at the root, recursively check each node and its subtrees.
For each node, verify if the entire subtree rooted there is univalue.
Count all valid subtrees encountered.

Step-by-Step Example

Example: Tree with root = 5, left = 5, right = 5

Text Representation:

Root: 5
Left: 5
Right: 5

DFS:

Root (5): Check whole tree—left 5, right 5, root 5 → univalue, count +1 → 1.
Left (5): Leaf, univalue, count +1 → 2.
Right (5): Leaf, univalue, count +1 → 3.

Result: 3.

Code for Top-Down Approach

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: TreeNode) -> int:
        # Step 1: Helper to check if subtree is univalue
        def is_univalue(node, value):
            if not node:
                return True
            if node.val != value:
                return False
            return is_univalue(node.left, value) and is_univalue(node.right, value)

        # Step 2: Main DFS to count
        def dfs(node):
            if not node:
                return 0
            count = 0
            if is_univalue(node, node.val):
                count += 1
            count += dfs(node.left)
            count += dfs(node.right)
            return count

        return dfs(root)

Time Complexity: O(n * h)—each node may check its subtree.
Space Complexity: O(h)—recursion stack.

It’s clear but slower.

Comparing the Two Solutions

Best Solution (Bottom-Up):

Pros: O(n) time, efficient, scalable.
Cons: Requires bottom-up logic.

Alternative Solution (Top-Down):

Pros: Intuitive top-down view.
Cons: O(n * h) time, less efficient.

Bottom-up wins for speed.

Additional Examples and Edge Cases

Single Node

Root: 5 → 1

Non-Univalue

Root: 1, Left: 2 → 1 (only leaf)

Deep Tree

Root: 5, Left: 5, Right: 5 (Left: 5) → 4

Both handle these well.

Complexity Breakdown

Bottom-Up:

Time: O(n)—single pass.
Space: O(h)—stack.

Top-Down:

Time: O(n * h)—subtree checks.
Space: O(h)—stack.

Bottom-up is faster.

Key Takeaways for Beginners

Bottom-Up: Build answers from leaves up.
Univalue: All nodes must match.
Top-Down: Check whole subtrees—simpler but slow.
Python Tip: Recursion rocks for trees—see [Python Basics](/python/basics).

Final Thoughts: Count Trees Like a Pro

LeetCode 250: Count Univalue Subtrees in Python is a great tree traversal challenge. The bottom-up solution offers O(n) brilliance, while top-down provides a clear alternative. Want more? Try LeetCode 104: Maximum Depth of Binary Tree or LeetCode 236: Lowest Common Ancestor. Ready to count? Head to Solve LeetCode 250 on LeetCode and tally those subtrees today!