Difficulty: 🟢 Easy
Topics: Tree, Depth-First Search, Breadth-First Search, Binary Tree

Solution

LeetCode 965 - Univalued Binary Tree

Problem Understanding

The problem gives us the root node of a binary tree and asks whether the tree is "uni-valued". A binary tree is considered uni-valued if every node in the tree contains exactly the same integer value.

In simpler terms, we need to examine every node in the tree and verify that all node values match one common value. If even a single node has a different value, the answer must be false. Otherwise, if all values are identical, the answer is true.

The input represents a standard binary tree structure where each node contains:

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

The expected output is a boolean value:

true if all nodes contain the same value
false if at least one node differs

The constraints are relatively small:

The tree contains between 1 and 100 nodes
Node values range from 0 to 99

Because the tree size is small, we do not need highly advanced optimization techniques. A straightforward tree traversal is more than sufficient.

Several edge cases are important to recognize upfront. A tree with only one node is always uni-valued because there are no differing values. Trees with missing children, such as skewed trees or sparse trees, still need proper traversal. Another important case occurs when most values are equal but a single deep node differs, naive implementations that stop traversal incorrectly could miss this.

The problem guarantees that the tree has at least one node, so root will never be None.

Approaches

Brute Force Approach

A brute force solution would first traverse the entire tree and collect all node values into a list or set. After traversal, we could check whether all collected values are identical.

For example, we could perform a DFS traversal and insert every node value into a set. If the final set size is 1, then the tree is uni-valued. Otherwise, it is not.

This approach works correctly because a set automatically removes duplicates. If more than one distinct value exists in the tree, the set size becomes larger than one.

However, this solution uses unnecessary extra memory because we store every distinct value even though we only need to compare values against the root value.

Optimal Approach

The key insight is that every node only needs to be compared against one reference value, specifically the root's value.

Instead of storing all values, we can traverse the tree and immediately verify whether each node matches the root value. If any mismatch is found, we can return false immediately without continuing unnecessary traversal.

This works because the definition of a uni-valued tree depends entirely on whether all nodes equal a single value. Since the root already provides that target value, every other node only needs one comparison.

Depth-First Search is a natural fit because trees are recursively structured. We recursively validate the left and right subtrees while carrying the expected value.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n)	O(n)	Traverses tree and stores values in a set
Optimal	O(n)	O(h)	DFS traversal with direct comparisons

Here, n is the number of nodes and h is the height of the tree.

Algorithm Walkthrough

Store the root node's value as the target value that every node must match.
Perform a Depth-First Search traversal starting from the root.
For each visited node, first check whether the node is None. If it is, return true because an empty subtree cannot violate the uni-valued property.
Compare the current node's value with the target value.
If the values differ, immediately return false because the tree is no longer uni-valued.
Recursively validate the left subtree.
Recursively validate the right subtree.
Return true only if both recursive subtree checks return true.

The recursive traversal ensures that every node in the tree is checked exactly once.

Why it works

The algorithm maintains the invariant that every visited node must equal the root value. If a mismatch is ever discovered, the invariant is broken and the algorithm immediately returns false.

If traversal completes without finding any differing value, then every node matched the root value, which exactly satisfies the definition of a uni-valued tree.

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 isUnivalTree(self, root: Optional[TreeNode]) -> bool:
        target_value = root.val

        def dfs(node: Optional[TreeNode]) -> bool:
            if node is None:
                return True

            if node.val != target_value:
                return False

            return dfs(node.left) and dfs(node.right)

        return dfs(root)

The implementation begins by storing the root node's value in target_value. This value becomes the reference that all other nodes must match.

The nested dfs function performs recursive traversal. The base case handles None nodes by returning True, because empty subtrees are always valid.

Each non-null node is compared against target_value. If a mismatch occurs, the function immediately returns False.

The recursive call then validates both child subtrees. The logical and ensures that both subtrees must satisfy the uni-valued condition for the current subtree to be valid.

Finally, the algorithm starts traversal from the root node and returns the result.

Go Solution

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

	var dfs func(node *TreeNode) bool

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

		if node.Val != targetValue {
			return false
		}

		return dfs(node.Left) && dfs(node.Right)
	}

	return dfs(root)
}

The Go implementation follows the same recursive DFS strategy as the Python version.

One notable difference is the explicit function variable declaration for recursion:

var dfs func(node *TreeNode) bool

This declaration is required because Go needs the recursive function variable defined before assignment.

Go pointers naturally represent tree node references, so nil checks are used instead of Python's None.

Since node values are very small integers, integer overflow is not a concern in this problem.

Worked Examples

Example 1

Input:

root = [1,1,1,1,1,null,1]

Tree structure:

Target value is 1.

Current Node	Comparison	Result
1	1 == 1	continue
1	1 == 1	continue
1	1 == 1	continue
1	1 == 1	continue
1	1 == 1	continue
1	1 == 1	continue

Every node matches the target value, so the algorithm returns true.

Example 2

Input:

root = [2,2,2,5,2]

Tree structure:

Target value is 2.

Current Node	Comparison	Result
2	2 == 2	continue
2	2 == 2	continue
5	5 != 2	return false

As soon as node 5 is encountered, the algorithm immediately returns false.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Every node is visited once
Space	O(h)	Recursive call stack depends on tree height

The time complexity is linear because the algorithm may need to inspect every node in the tree exactly once.

The space complexity comes from recursion depth. In a balanced tree, the height is approximately log n. In the worst case, such as a completely skewed tree, the height becomes 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

solution = Solution()

# Example 1
root1 = TreeNode(1,
    TreeNode(1,
        TreeNode(1),
        TreeNode(1)
    ),
    TreeNode(1,
        None,
        TreeNode(1)
    )
)
assert solution.isUnivalTree(root1) == True  # all nodes identical

# Example 2
root2 = TreeNode(2,
    TreeNode(2,
        TreeNode(5),
        TreeNode(2)
    ),
    TreeNode(2)
)
assert solution.isUnivalTree(root2) == False  # one differing node

# Single node tree
root3 = TreeNode(7)
assert solution.isUnivalTree(root3) == True  # single node always valid

# Left skewed valid tree
root4 = TreeNode(3,
    TreeNode(3,
        TreeNode(3)
    )
)
assert solution.isUnivalTree(root4) == True  # skewed tree with same values

# Right skewed invalid tree
root5 = TreeNode(4,
    None,
    TreeNode(4,
        None,
        TreeNode(9)
    )
)
assert solution.isUnivalTree(root5) == False  # deep mismatch

# Mixed structure valid tree
root6 = TreeNode(8,
    TreeNode(8),
    TreeNode(8,
        TreeNode(8),
        None
    )
)
assert solution.isUnivalTree(root6) == True  # sparse valid tree

Test	Why
`[1,1,1,1,1,null,1]`	Validates standard uni-valued tree
`[2,2,2,5,2]`	Validates mismatch detection
Single node tree	Tests minimum input size
Left skewed tree	Tests recursive traversal on uneven trees
Right skewed invalid tree	Tests deep mismatch detection
Sparse valid tree	Ensures null children handled correctly

Edge Cases

A single-node tree is an important edge case because there are no child nodes to compare. Some implementations incorrectly assume at least one comparison must occur. This implementation handles the case naturally because the DFS visits the single node, confirms it matches the target value, and returns true.

Skewed trees are another important case. A tree may resemble a linked list with depth close to n. Recursive traversal must still correctly visit every node. Since the constraints limit the tree to only 100 nodes, recursion depth is completely safe here.

Trees with one differing node deep in the structure can expose bugs in incomplete traversals. For example, if a solution only checks immediate children of the root, it may incorrectly return true. This implementation recursively explores the entire tree, guaranteeing that even deeply nested mismatches are detected.

Sparse trees with missing children are also important. Some nodes may have only one child while others have none. The implementation safely handles these cases using the None or nil base case, ensuring that missing children do not cause runtime errors or incorrect comparisons.