Problem Description

A uni-valued binary tree is a tree where all nodes contain the exact same value.

Given the root of a binary tree, you need to determine if the tree is uni-valued. Return true if every node in the tree has the same value, and false otherwise.

For example:

• A tree with all nodes having value 1 would be uni-valued → return true
• A tree where some nodes have value 1 and others have value 2 would not be uni-valued → return false
• An empty tree or a single node tree is considered uni-valued → return true

The solution uses a depth-first search (DFS) approach. It stores the root node's value as x, then recursively checks if every node in the tree has the same value as x. The function traverses through all nodes, comparing each node's value with x. If any node has a different value, it returns false. The traversal continues through both left and right subtrees, and only returns true when all nodes have been verified to have the same value.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• Yes: A binary tree is a special type of graph with nodes and edges. Each node can have at most two children (left and right), connected by edges.

Is it a tree?

• Yes: The problem explicitly states we're working with a binary tree structure. A tree is a connected acyclic graph, and in this case, we have a rooted binary tree.

DFS

• Conclusion reached: Since we're dealing with a tree structure, the flowchart leads us directly to DFS (Depth-First Search).

The flowchart suggests using DFS for this tree problem, which makes perfect sense because:

1. We need to visit every node in the tree to check if all values are the same
2. DFS allows us to recursively traverse the tree structure efficiently
3. We can compare each node's value with a reference value (the root's value) as we traverse
4. The recursive nature of DFS naturally handles the tree's hierarchical structure

Conclusion: The flowchart correctly identifies that for a tree-based problem like checking if a binary tree is uni-valued, DFS is the appropriate algorithm pattern to use.

Intuition

The key insight is that for a tree to be uni-valued, every single node must have the same value. This immediately suggests we need to visit every node and check its value.

When we think about checking if all nodes have the same value, we need a reference point - what value should we compare against? The most natural choice is the root node's value. If the tree is uni-valued, then by definition, every node must have the same value as the root.

Now, how do we traverse the tree to check every node? Since we established through the flowchart that DFS is appropriate for tree problems, we can use recursion to naturally follow the tree's structure. At each node, we need to verify three things:

1. The current node's value equals our reference value (the root's value)
2. All nodes in the left subtree are uni-valued with the same value
3. All nodes in the right subtree are uni-valued with the same value

This recursive structure maps perfectly to DFS - we check the current node, then recursively check both subtrees. The beauty of this approach is that if any node fails the check (has a different value), the entire recursion chain returns false immediately due to the logical AND operation.

The base case is straightforward: if we reach a null node (beyond a leaf), we return true because an empty subtree doesn't violate the uni-valued property. This allows the recursion to naturally terminate at the leaves of the tree.

By storing the root's value as x before starting the DFS, we ensure consistent comparison throughout the entire traversal, making the solution both elegant and efficient with O(n) time complexity where we visit each node exactly once.

Learn more about Tree, Depth-First Search, Breadth-First Search and Binary Tree patterns.

Solution Approach

The solution implements a DFS traversal using a helper function to check if all nodes in the tree have the same value.

Step 1: Store the Reference Value First, we store the root node's value in a variable x. This will be our reference value that all other nodes must match for the tree to be uni-valued.

x = root.val

Step 2: Define the DFS Helper Function We create a recursive function dfs(root) that checks whether the current subtree rooted at root is uni-valued with value x.

The function logic follows this pattern:

• Base Case: If the current node is None (we've reached beyond a leaf), return True since an empty subtree doesn't violate the uni-valued property.
• Recursive Case: Check three conditions using logical AND:
  1. The current node's value equals x
  2. The left subtree is uni-valued (recursive call to dfs(root.left))
  3. The right subtree is uni-valued (recursive call to dfs(root.right))

def dfs(root: Optional[TreeNode]) -> bool:
    if root is None:
        return True
    return root.val == x and dfs(root.left) and dfs(root.right)

Step 3: Execute the DFS Call dfs(root) from the main function to start the traversal from the root and return its result.

The algorithm leverages short-circuit evaluation in the logical AND operation - if root.val != x, the function immediately returns False without checking the subtrees, providing an early termination optimization.

Time Complexity: O(n) where n is the number of nodes, as we visit each node exactly once.

Space Complexity: O(h) where h is the height of the tree, representing the maximum recursion stack depth. In the worst case (skewed tree), this could be O(n).

Example Walkthrough

Let's walk through a small example to illustrate how the solution works.

Consider this binary tree:

       5
      / \
     5   5
    / \
   5   3

Step 1: Initialize Reference Value

• We start at the root node with value 5
• Store x = 5 as our reference value

Step 2: Begin DFS Traversal from Root

• Call dfs(root) where root has value 5
• Check: root.val == x → 5 == 5 ✓ (True)
• Now need to check both subtrees

Step 3: Check Left Subtree

• Call dfs(root.left) on the left child (value 5)
• Check: 5 == 5 ✓ (True)
• Check its left child: dfs on node with value 5
  • 5 == 5 ✓ (True)
  • Both children are None, return True
• Check its right child: dfs on node with value 3
  • 3 == 5 ✗ (False)
  • Immediately return False (no need to check further)

Step 4: Short-Circuit Evaluation

• Since the left subtree returned False, the AND operation in the root's check (root.val == x and dfs(root.left) and dfs(root.right)) evaluates to False
• The right subtree is never checked due to short-circuit evaluation
• Final result: False - the tree is not uni-valued

Alternative Example - Uni-valued Tree:

       2
      / \
     2   2
        / \
       2   2

• Store x = 2
• Every dfs call checks: current node value equals 2 ✓
• All recursive calls return True
• Final result: True - the tree is uni-valued

The algorithm efficiently identifies that the first tree is not uni-valued by finding the mismatched node (value 3) and immediately propagating False up through the recursion chain.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n)

The algorithm performs a depth-first search (DFS) traversal of the binary tree. Each node in the tree is visited exactly once. During each visit, the algorithm performs a constant-time operation (comparing root.val == x). Therefore, the total time complexity is O(n), where n is the number of nodes in the tree.

Space Complexity: O(n)

The space complexity is determined by the recursive call stack used during the DFS traversal. In the worst case, the tree is completely unbalanced (resembling a linked list), where each node has only one child. This would result in a recursion depth of n, requiring O(n) space on the call stack. In the best case of a perfectly balanced tree, the recursion depth would be O(log n), but since we consider worst-case complexity, the space complexity is O(n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Not Handling Empty Tree Edge Case

A common mistake is not considering what happens when the input tree is None (empty tree). The current solution assumes root is not None when accessing root.val, which would raise an AttributeError.

Problem Code:

def isUnivalTree(self, root: Optional[TreeNode]) -> bool:
    target_value = root.val  # This fails if root is None!
    # ... rest of code

Solution: Add a check for empty tree at the beginning:

def isUnivalTree(self, root: Optional[TreeNode]) -> bool:
    if root is None:
        return True  # Empty tree is considered uni-valued
  
    target_value = root.val
    # ... rest of code

2. Using Global Variables Instead of Closure

Some developers might try to use a class-level or global variable to store the target value, leading to issues with multiple test cases or concurrent execution.

Problem Code:

class Solution:
    def __init__(self):
        self.target_value = None  # Class variable - problematic!
  
    def isUnivalTree(self, root: Optional[TreeNode]) -> bool:
        self.target_value = root.val
        return self.dfs(root)
  
    def dfs(self, node):
        # Using self.target_value can cause issues
        return node.val == self.target_value and ...

Solution: Keep the target value as a local variable and use closure (as shown in the original solution) or pass it as a parameter:

def dfs(node: Optional[TreeNode], target: int) -> bool:
    if node is None:
        return True
    return node.val == target and dfs(node.left, target) and dfs(node.right, target)

# Call with: dfs(root, root.val)

3. Inefficient Short-Circuit Evaluation

Writing the condition check in a way that doesn't take advantage of short-circuit evaluation, causing unnecessary recursive calls.

Problem Code:

def dfs(node: Optional[TreeNode]) -> bool:
    if node is None:
        return True
    # This evaluates all conditions even if node.val != target_value
    left_result = dfs(node.left)
    right_result = dfs(node.right)
    return node.val == target_value and left_result and right_result

Solution: Use the logical AND operator directly in the return statement to enable short-circuiting:

def dfs(node: Optional[TreeNode]) -> bool:
    if node is None:
        return True
    # Short-circuits if node.val != target_value
    return node.val == target_value and dfs(node.left) and dfs(node.right)

4. Incorrect Base Case Logic

Some might incorrectly handle the base case by returning False for None nodes, thinking an empty node means the tree isn't uni-valued.

Problem Code:

def dfs(node: Optional[TreeNode]) -> bool:
    if node is None:
        return False  # Wrong! Empty subtree doesn't violate uni-valued property
    return node.val == target_value and dfs(node.left) and dfs(node.right)

Solution: Return True for None nodes since an empty subtree doesn't contain any nodes with different values:

def dfs(node: Optional[TreeNode]) -> bool:
    if node is None:
        return True  # Correct: empty subtree is valid
    return node.val == target_value and dfs(node.left) and dfs(node.right)