#687

Medium

auto_awesomeBinary-tree traversal and state tracking

LeetCode Problem Workspace

Longest Univalue Path

Find the longest path in a binary tree where all nodes share the same value using depth-first search efficiently.

Problem Statement

Given a binary tree, determine the length of the longest path where all nodes on that path share the same value. The path does not have to pass through the root, and length is measured in number of edges connecting consecutive nodes.

You are provided with the tree's root node. Return an integer representing the maximum number of edges forming a path with identical node values. For example, given root = [5,4,5,1,1,null,5], the output should be 2 since the longest path with the same value (5) connects two edges.

Examples

Example 1

Input: root = [5,4,5,1,1,null,5]

Output: 2

The shown image shows that the longest path of the same value (i.e. 5).

Example 2

Input: root = [1,4,5,4,4,null,5]

Output: 2

The shown image shows that the longest path of the same value (i.e. 4).

Constraints

The number of nodes in the tree is in the range [0, 104].
-1000 <= Node.val <= 1000
The depth of the tree will not exceed 1000.

Solution Approach

Depth-First Search with Recursion

Traverse the tree recursively. At each node, calculate the longest path in the left and right subtrees that continues the current node's value. This ensures you capture all potential univalue paths, even when the root is not part of the path.

State Tracking with Edge Counts

Keep a global maximum that updates whenever a node combines left and right paths of the same value. Track edge counts rather than node counts to match problem definition. Carefully propagate values back up the recursion to maintain accurate path lengths.

Handling Nulls and Value Mismatches

Return 0 for null nodes. When a child value differs from the current node, reset that branch's count. This prevents overcounting and ensures only continuous univalue paths contribute to the maximum.

Complexity Analysis

Metric	Value
Time	O(N)
Space	O(N)

Time complexity is O(N) because every node is visited once during DFS. Space complexity is O(N) due to recursion stack in the worst case of a skewed tree.

What Interviewers Usually Probe

Look for recognition that the path length is counted in edges, not nodes.
Check if the candidate correctly handles paths that do not pass through the root.
Expect use of DFS with state propagation to track continuous univalue segments.

Common Pitfalls or Variants

Common pitfalls

Counting nodes instead of edges leads to off-by-one errors.
Failing to combine left and right paths at a node may miss the actual maximum path.
Not resetting counts on value mismatch can inflate path length incorrectly.

Follow-up variants

Compute the longest path for a specific value rather than any univalue path.
Find the longest path in an n-ary tree where nodes share the same value.
Return all paths with maximum length instead of just the length.

FAQ

What is the longest univalue path in a binary tree?

It is the path with the maximum number of edges connecting nodes that all share the same value, possibly excluding the root.

Does the path need to go through the root node?

No, the path can be anywhere in the tree and does not have to include the root.

How does depth-first search help solve this problem?

DFS allows you to recursively calculate path lengths from each node, combining left and right children to track maximum univalue paths efficiently.

How are edges counted in the longest univalue path?

Edges are counted as the number of connections between nodes, not the number of nodes themselves.

What common mistake should I avoid for Longest Univalue Path?

A frequent mistake is not resetting counts when node values differ, which can lead to overcounting paths that are not truly univalue.

terminal

Solution

Solution 1: DFS

We design a function $\textit{dfs}(root)$, which represents the longest univalue path length extending downward with the $\textit{root}$ node as one endpoint of the path.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

# 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
class Solution:
    def longestUnivaluePath(self, root: Optional[TreeNode]) -> int:
        def dfs(root: Optional[TreeNode]) -> int:
            if root is None:
                return 0
            l, r = dfs(root.left), dfs(root.right)
            l = l + 1 if root.left and root.left.val == root.val else 0
            r = r + 1 if root.right and root.right.val == root.val else 0
            nonlocal ans
            ans = max(ans, l + r)
            return max(l, r)

        ans = 0
        dfs(root)
        return ans

Continue Practicing

#671 second minimum node in a binary tree #669 trim a binary search tree #662 maximum width of binary tree