Univalued Binary Tree: Simple Tree Traversal Check

You are given the root of a binary tree. Return true if every node in the tree has the same value. Return false otherwise.

This is LeetCode 965: Univalued Binary Tree, and it is one of the simplest tree problems you will encounter. The question boils down to a single check: does every node in the tree hold the same value as the root? If any single node disagrees, the answer is false.

The problem

A binary tree is univalued if every node has the same value. Given the root of a binary tree, return true if it is univalued and false otherwise.

For example, the tree [1, 1, 1, 1, 1, null, 1] is univalued because every node holds the value 1. The tree [2, 2, 2, 5, 2] is not univalued because the node with value 5 breaks the pattern.

Why this problem matters

Univalued Binary Tree looks almost too easy to bother with, but it teaches a pattern that shows up everywhere in tree problems: validate a property across every node using DFS with early termination. The same skeleton applies when you check whether a tree is a valid BST, whether it is balanced, or whether it is symmetric. The only difference is what condition you check at each node.

This is also a great warm-up for understanding how recursive tree traversals short-circuit. When you find a mismatch, you do not need to visit the rest of the tree. You return false immediately, and that false propagates up through every ancestor. That early termination behavior is critical in harder problems where visiting unnecessary nodes would blow up your time complexity.

If you can write the Univalued Binary Tree solution from memory, you have internalized the "DFS validation with early exit" skeleton. That skeleton transfers directly to Balanced Binary Tree, Validate Binary Search Tree, and many others.

The brute force approach

One way to solve this is to collect every value in the tree into a list, then check if all values are the same.

def is_unival(root):
    values = []
    def collect(node):
        if node:
            values.append(node.val)
            collect(node.left)
            collect(node.right)
    collect(root)
    return len(set(values)) <= 1

This works, but it always visits every node and uses O(n) extra space for the list. You cannot short-circuit early when you find a mismatch. If the very first child disagrees with the root, you still traverse the entire tree before checking the set.

The key insight

You do not need to collect all the values. You just need to compare each node to the root value during the traversal. The moment any node disagrees, you stop and return false. If you make it through every node without a mismatch, return true.

This turns the problem into a simple DFS where each node does one comparison: does my left child (if it exists) have the same value as me? Does my right child (if it exists) have the same value as me? If both checks pass, recurse into the children.

Walking through it step by step

Let's trace the DFS on the tree [2, 2, 2, 5, 2]. The root value is 2, and we need to check whether every node agrees.

Notice how the algorithm stops the moment it finds node 5. It never visits the right child of the root or the sibling of node 5. That early termination is the whole point of doing the check inline during the DFS rather than collecting values into a list first.

The solution

class Solution:
    def isUnivalTree(self, root):
        if not root:
            return True
        if root.left and root.left.val != root.val:
            return False
        if root.right and root.right.val != root.val:
            return False
        return self.isUnivalTree(root.left) and self.isUnivalTree(root.right)

Let's break this down:

• if not root: return True is the base case. A null node has no value to disagree, so it is trivially univalued.
• if root.left and root.left.val != root.val: return False checks the left child. If it exists and its value differs from the current node, the tree is not univalued.
• The same check applies to the right child.
• self.isUnivalTree(root.left) and self.isUnivalTree(root.right) recurses into both subtrees. Python's and operator short-circuits: if the left subtree returns False, the right subtree is never visited.

Each node compares itself to its children, and each child compares itself to its own children. By transitivity, if every parent-child pair agrees, then every node in the tree shares the root's value.

Complexity analysis

Time is O(n) in the worst case. If the tree is univalued, you visit every node exactly once. If there is a mismatch, you short-circuit and visit fewer nodes, but the worst case is still O(n).

Space is O(h), where h is the height of the tree. This comes from the recursion call stack. For a balanced tree, h = log(n). For a completely skewed tree (every node has only one child), h = n, making the space O(n) in the worst case.

Building blocks

1. DFS with early termination

The core pattern here is a DFS that checks a condition at every node and returns false the moment the condition is violated. This is the same skeleton used in Validate BST (where you check value bounds), Balanced Binary Tree (where you check height differences), and Symmetric Tree (where you check mirror pairs). The skeleton looks like this:

def validate(node):
    if not node:
        return True
    if VIOLATION(node):
        return False
    return validate(node.left) and validate(node.right)

For Univalued Binary Tree, VIOLATION checks whether the left or right child has a different value than the current node.

2. Value propagation in tree traversal

Instead of passing the root value down explicitly, you compare each node to its immediate children. The transitivity of equality handles the rest: if A == B and B == C, then A == C. This avoids the need for extra parameters in the recursive function and keeps the code clean.

Edge cases

• Single node (no children): return true. There is only one value, so the tree is trivially univalued.
• Null tree (root is None): return true. An empty tree has no nodes to disagree.
• All nodes have the same value: the DFS visits every node and returns true at the end. This is the worst case for time.
• Mismatch at a deep leaf: the DFS must traverse all the way down before finding the mismatch. The early termination does not help here, but the algorithm is still O(n).
• Mismatch at the root's immediate child: the DFS finds the mismatch on the very first comparison and returns false without visiting the rest of the tree.

Common mistakes

1. Forgetting the null check on children. If you compare root.left.val != root.val without first checking that root.left exists, you will get a null pointer error on leaf nodes.
2. Comparing to the root value using a global variable instead of parent-child comparisons. This works, but it introduces unnecessary state. The parent-child approach is cleaner.
3. Not short-circuiting. If you use self.isUnivalTree(root.left) + self.isUnivalTree(root.right) or similar logic that evaluates both subtrees regardless, you lose the early termination benefit.
4. Returning the wrong base case for null. A null tree should return true, not false. There are no nodes to violate the univalued property.

From understanding to recall

You just read a simple recursive solution that checks whether every node in a tree shares the same value. The logic is clean: compare each node to its children, recurse, short-circuit on mismatch. It all makes sense right now.

But will you remember the exact structure of this DFS in two weeks? Will you instinctively write the null check before the value comparison? Will you remember that Python's and operator gives you early termination for free? Understanding fades. Recall under pressure is what matters in an interview.

Spaced repetition bridges that gap. You type the solution from scratch at increasing intervals: after one day, then three days, then a week. Each repetition reinforces the "DFS validation with early exit" skeleton until it becomes automatic. This same skeleton covers dozens of tree problems. Learning it once and drilling it with spaced repetition is far more effective than grinding random problems.

Related posts

• Same Tree - Comparing two trees node by node with the same DFS pattern
• Symmetric Tree - Another tree validation using mirrored DFS
• Invert Binary Tree - Tree traversal and modification

The DFS validation pattern you learned here is one building block in a library of roughly 60 reusable patterns that cover hundreds of LeetCode problems. Master the building blocks, and the problems stop being puzzles.