Problem Description

You are given the root of a binary tree. Your task is to find the length of the longest path in the tree where all nodes along the path have the same value. This path can go through any nodes in the tree and doesn't have to pass through the root.

The length of a path is measured by the number of edges between nodes, not the number of nodes. For example, a path with 3 nodes has a length of 2 (two edges connecting the three nodes).

A "univalue path" means all nodes in the path must have identical values. The path can:

• Start and end at any nodes in the tree
• Go through parent-child relationships
• Form a path that goes down from a node to its left subtree and then back up through the same node to its right subtree

For instance, if you have a tree where a parent node with value 5 has two children both with value 5, you could form a path from the left child, through the parent, to the right child. This would be a valid univalue path of length 2.

The solution uses a depth-first search approach where for each node, it calculates:

1. The longest univalue path extending downward from that node through its left subtree
2. The longest univalue path extending downward from that node through its right subtree
3. The potential longest path passing through that node (connecting paths from both subtrees)

The function tracks the maximum path length found anywhere in the tree and returns this as the final answer.

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 where each node has at most two children and there are no cycles. Trees are acyclic connected graphs.

Is it a tree?

• Yes: The problem explicitly states we're working with a binary tree structure. We have a root node and need to traverse through parent-child relationships.

DFS

• Following the flowchart, when we have a tree structure, the natural conclusion is to use DFS (Depth-First Search).

Why DFS is appropriate for this problem:

• We need to explore each path in the tree to find the longest univalue path
• For each node, we need to check paths extending through its left and right subtrees
• We need to recursively process subtrees and combine their results
• The problem requires us to track information as we traverse down the tree and pass information back up (the length of univalue paths)

Conclusion: The flowchart correctly leads us to use DFS for this tree-based problem. The DFS approach allows us to:

1. Recursively explore each subtree
2. Calculate the longest univalue path extending downward from each node
3. Combine results from left and right subtrees to find paths passing through each node
4. Track the global maximum across all possible paths in the tree

Intuition

When looking at this problem, we need to find the longest path where all nodes have the same value. The key insight is that any such path in a tree has a "peak" node - the highest node in the path where the path potentially branches down into both left and right subtrees.

Think about how a univalue path can be formed in a tree. For any node, a path passing through it can extend:

• Down to its left subtree (if the left child has the same value)
• Down to its right subtree (if the right child has the same value)
• Or both, creating a path that goes from left subtree → current node → right subtree

This suggests we need to know, for each node, what's the longest univalue path that extends straight down from it. But here's the catch: when we're calculating the answer (the longest path in the entire tree), we can use both left and right extensions. However, when we're returning a value to use in parent calculations, we can only return one branch - either left or right - because a path must be continuous without branching.

Let's think through an example. If we have a node with value 5, and both its children also have value 5:

• The left child might have a univalue path of length 2 extending down from it
• The right child might have a univalue path of length 1 extending down from it
• The path through this node would be: 2 + 1 + 1 + 1 = 5 edges (left path + edge to left child + edge to right child + right path)
• But when reporting up to this node's parent, we can only say "the longest path going down from me is max(2+1, 1+1) = 3"

This dual nature - calculating the full path through a node versus what we can extend upward - is why we need to track a global maximum (ans) separately from the return value of our recursive function. The recursive function returns the longest single branch extending down, while we update ans with the longest path that might pass through the current node using both branches.

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

Solution Approach

The solution implements a DFS traversal with a clever tracking mechanism to find the longest univalue path. Let's break down the implementation:

Core DFS Function Design

We design a function dfs(root) that returns the longest univalue path length extending downward from the root node as one endpoint. This is crucial - the function doesn't return the longest path through the node, but rather the longest single branch extending down.

Base Case

If root is None, we return 0 since there's no path from a null node.

Recursive Calls

We recursively call dfs(root.left) and dfs(root.right) to get:

• l: the longest univalue path extending down from the left child
• r: the longest univalue path extending down from the right child

Extending Paths Based on Value Matching

Here's where we check if we can extend the paths:

• If root.left exists and root.left.val == root.val, then we can extend the left path by 1 edge (from root to left child), so l = l + 1
• Otherwise, we can't extend through the left side, so l = 0
• Similarly for the right side with r

Updating the Global Maximum

The key insight: while we can only return one branch upward, we can use both branches to form a path through the current node. We update ans = max(ans, l + r). This l + r represents:

• l edges extending down through the left subtree
• r edges extending down through the right subtree
• These connect through the current node to form a complete path

Return Value

The function returns max(l, r) - the longest single branch we can extend upward to the parent. We can't return both branches because that would create a fork, not a valid path.

Using Nonlocal Variable

The solution uses nonlocal ans to maintain the global maximum across all recursive calls. This allows each node to potentially update the answer while still returning the appropriate value for its parent's calculations.

Overall Algorithm Flow

1. Initialize ans = 0 to track the global maximum
2. Call dfs(root) to traverse the entire tree
3. At each node, calculate potential paths through both children
4. Update the global maximum with the full path through this node
5. Return the longest single branch for parent calculations
6. After traversal completes, return ans

This approach ensures we consider all possible univalue paths in the tree while maintaining the correct recursive structure for tree traversal.

Example Walkthrough

Let's walk through a concrete example to illustrate how this solution works.

Consider this binary tree:

        1
       / \
      4   5
     / \   \
    4   4   5

We want to find the longest univalue path. Let's trace through the DFS:

Step 1: Start DFS from root (value = 1)

• First, we traverse all the way down to the leaves

Step 2: Process leaf node (leftmost 4)

• dfs(node_4_leftmost) returns 0 (no children)
• No path through this node, ans remains 0

Step 3: Process leaf node (middle 4)

• dfs(node_4_middle) returns 0 (no children)
• No path through this node, ans remains 0

Step 4: Process node with value 4 (left child of root)

• l = dfs(left_child) = 0 (from leftmost 4)
• r = dfs(right_child) = 0 (from middle 4)
• Both children have value 4, same as parent:
  • l = 0 + 1 = 1 (can extend left by 1 edge)
  • r = 0 + 1 = 1 (can extend right by 1 edge)
• Update ans = max(0, 1 + 1) = 2 (path from leftmost 4 → parent 4 → middle 4)
• Return max(1, 1) = 1 to parent

Step 5: Process leaf node (rightmost 5)

• dfs(node_5_leaf) returns 0 (no children)
• No path through this node, ans remains 2

Step 6: Process node with value 5 (right child of root)

• l = dfs(left_child) = 0 (no left child)
• r = dfs(right_child) = 0 (from rightmost 5)
• Right child has value 5, same as parent:
  • l = 0 (no left child)
  • r = 0 + 1 = 1 (can extend right by 1 edge)
• Update ans = max(2, 0 + 1) = 2 (doesn't improve our answer)
• Return max(0, 1) = 1 to parent

Step 7: Process root node (value = 1)

• l = dfs(left_child) = 1 (from the 4-valued subtree)
• r = dfs(right_child) = 1 (from the 5-valued subtree)
• Check children values:
  • Left child (4) ≠ root (1), so l = 0
  • Right child (5) ≠ root (1), so r = 0
• Update ans = max(2, 0 + 0) = 2
• Return max(0, 0) = 0

Final Answer: 2

The longest univalue path has length 2, consisting of the path through the three nodes with value 4 (leftmost 4 → parent 4 → middle 4), which has 2 edges.

Key observations from this walkthrough:

1. The function returns the longest single branch extending down, not the full path through a node
2. When both children match the parent's value, we can form a path using both branches (updating ans with l + r)
3. When returning to the parent, we only report the longer single branch (max(l, r))
4. The global variable ans tracks the maximum path found anywhere in the tree

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 is visited exactly once during the traversal. At each node, the algorithm performs constant time operations:

• Checking if the node is null
• Recursive calls to left and right children
• Comparing values with children nodes
• Updating the maximum path length
• Returning the maximum of left and right paths

Since we visit each of the n nodes exactly once and perform O(1) operations at each node, the total time complexity is O(n).

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 could be completely unbalanced (e.g., a skewed tree where each node has only one child), resulting in a recursion depth equal to the number of nodes n. This would require 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 we consider the worst-case scenario for space complexity analysis.

Additionally, the algorithm uses only a constant amount of extra space for variables (ans, l, r), which doesn't affect the overall space complexity.

Therefore, the space complexity is O(n).

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

Common Pitfalls

Pitfall 1: Confusing Path Length with Node Count

A frequent mistake is returning or calculating the number of nodes instead of the number of edges. Remember that path length is defined as the number of edges, not nodes. A path with 3 nodes has a length of 2.

Incorrect approach:

# Wrong: Counting nodes instead of edges
if node.left and node.left.val == node.val:
    left_arrow_length = left_length + 1  # This counts nodes
# Then later using this directly as path length

Correct approach: The solution correctly handles this by adding 1 for each edge when extending paths, and the final left_arrow_length + right_arrow_length correctly represents the total number of edges.

Pitfall 2: Incorrectly Handling the Return Value

Many implementations mistakenly return the maximum path through a node instead of the maximum single-direction path from that node.

Incorrect approach:

def calculate_univalue_length(node):
    # ... calculation logic ...
    # Wrong: Returning the full path through the node
    return left_arrow_length + right_arrow_length

Correct approach:

def calculate_univalue_length(node):
    # ... calculation logic ...
    # Update global max with full path through node
    self.max_path_length = max(self.max_path_length, left_arrow_length + right_arrow_length)
    # But return only the longest single direction for parent to use
    return max(left_arrow_length, right_arrow_length)

Pitfall 3: Not Resetting Path Length When Values Don't Match

A critical error is forgetting to reset the path length to 0 when a child node has a different value than its parent.

Incorrect approach:

# Wrong: Always extending the path regardless of value
left_arrow_length = left_length + 1 if node.left else 0
# This doesn't check if values match!

Correct approach:

# Correct: Only extend if child exists AND values match
left_arrow_length = left_length + 1 if node.left and node.left.val == node.val else 0

Pitfall 4: Using Global Variables Incorrectly

Using a regular variable instead of instance variable or nonlocal can cause scoping issues.

Incorrect approach:

def longestUnivaluePath(self, root):
    max_path_length = 0  # Local variable
  
    def calculate_univalue_length(node):
        # This will cause UnboundLocalError
        max_path_length = max(max_path_length, left_arrow_length + right_arrow_length)

Correct approaches:

# Option 1: Using instance variable (as shown in the solution)
self.max_path_length = 0

# Option 2: Using nonlocal
def longestUnivaluePath(self, root):
    max_path_length = 0
  
    def calculate_univalue_length(node):
        nonlocal max_path_length
        max_path_length = max(max_path_length, left_arrow_length + right_arrow_length)

Pitfall 5: Edge Case of Single Node or Empty Tree

Forgetting to handle edge cases where the tree is empty or contains only one node.

The solution correctly handles these cases:

• Empty tree (root is None): The base case returns 0, and self.max_path_length remains 0
• Single node: Both left and right lengths are 0, resulting in a maximum path of 0 (which is correct since a single node has no edges)