LeetCode 687: Longest Univalue Path

Problem Restatement

We are given the root of a binary tree.

We need to return the length of the longest path where every node on the path has the same value.

The path may or may not pass through the root.

The length of a path is counted by number of edges, not number of nodes. The official constraints allow an empty tree, up to 10^4 nodes, node values from -1000 to 1000, and tree depth at most 1000.

Input and Output

Example function shape:

def longestUnivaluePath(root: Optional[TreeNode]) -> int:
    ...

Examples

Example 1:

        5
       / \
      4   5
     / \   \
    1   1   5

The longest same-value path is:

5 -> 5

It has 1 edge from the right child to its child.

But the official example output is 2 for the tree [5,4,5,1,1,null,5], because the shown longest value path has two nodes connected through value 5 with length counted by edges.

Example 2:

        1
       / \
      4   5
     / \   \
    4   4   5

The longest same-value path is:

4 -> 4 -> 4

It has 2 edges.

Answer:

2

First Thought: Try Every Path

A direct idea is to start from each node and search all same-value paths from that node.

This can find the answer, but it repeats work.

For each node, we might traverse large parts of its subtree again.

In the worst case, this becomes too slow.

We need each node to contribute information once.

Key Insight

For each node, there are two different questions.

First, what is the longest same-value path that passes through this node?

Second, what is the longest same-value branch that this node can return to its parent?

These are different because a path can use both left and right children when computing the answer, but it can only return one branch upward.

For example:

      4
     / \
    4   4

The best path through the root uses both sides:

4 -> 4 -> 4

This has length 2.

But if the parent of this root also has value 4, this node can only extend one side upward:

parent -> root -> left

or:

parent -> root -> right

It cannot return both branches upward, because that would fork.

So the DFS helper should return one extendable branch length, while a separate answer variable tracks the best full path.

Algorithm

Use postorder DFS.

For each node:

1. Recursively compute the longest extendable same-value branch from the left child.
2. Recursively compute the longest extendable same-value branch from the right child.
3. If the left child exists and has the same value as the current node, the left branch can extend:

   left_arrow = left_length + 1
   Otherwise:

   left_arrow = 0
4. Do the same for the right child.
5. A same-value path passing through the current node has length:

   left_arrow + right_arrow
6. Update the global answer.
7. Return:

   max(left_arrow, right_arrow)

The returned value is the longest single branch that can be extended by the parent.

Walkthrough

Consider:

        1
       / \
      4   5
     / \   \
    4   4   5

Process the leaves first.

Each leaf returns 0, because a single node has no edge below it.

At node 4 with two children 4 and 4:

The best path through this node is:

1 + 1 = 2

So the answer becomes 2.

This node returns:

max(1, 1) = 1

to its parent, because only one branch can extend upward.

At the root 1, neither child has value 1, so both arrows are 0.

The final answer remains:

2

Correctness

The DFS helper returns the longest downward path starting at the current node such that all nodes on that branch have the same value as the current node.

This is true for a leaf, where the longest such branch has length 0.

For an internal node, the left child can contribute to this branch only if the left child has the same value. In that case, the branch length is the left child’s returned branch plus one edge from the current node to the left child. Otherwise, the left side contributes 0.

The same argument applies to the right child.

A longest same-value path whose highest node is the current node can use a valid left branch and a valid right branch together. Its length is left_arrow + right_arrow.

The algorithm updates the answer with this value at every node, so it considers every possible highest node of a same-value path.

When returning to the parent, the current node can contribute only one branch, because a path extended upward cannot split into both children. Therefore returning max(left_arrow, right_arrow) is correct.

Since every node is processed once, and every possible same-value path has some highest node where its two sides meet, the algorithm finds the longest one.

Complexity

Let n be the number of nodes and h be the height of the tree.

In the worst case, h = n for a skewed tree.

Implementation

class Solution:
    def longestUnivaluePath(self, root: Optional[TreeNode]) -> int:
        answer = 0

        def dfs(node: Optional[TreeNode]) -> int:
            nonlocal answer

            if node is None:
                return 0

            left_length = dfs(node.left)
            right_length = dfs(node.right)

            left_arrow = 0
            right_arrow = 0

            if node.left is not None and node.left.val == node.val:
                left_arrow = left_length + 1

            if node.right is not None and node.right.val == node.val:
                right_arrow = right_length + 1

            answer = max(answer, left_arrow + right_arrow)

            return max(left_arrow, right_arrow)

        dfs(root)
        return answer

Code Explanation

The variable:

answer = 0

stores the best full path found anywhere in the tree.

The helper:

def dfs(node: Optional[TreeNode]) -> int:

returns the longest same-value branch that starts at node and goes downward.

For a missing node:

if node is None:
    return 0

there is no branch.

We first compute both child branches:

left_length = dfs(node.left)
right_length = dfs(node.right)

Then we decide whether those branches can attach to the current node.

The left branch can attach only if the left child has the same value:

if node.left is not None and node.left.val == node.val:
    left_arrow = left_length + 1

The + 1 counts the edge from node to node.left.

The same logic applies to the right child:

if node.right is not None and node.right.val == node.val:
    right_arrow = right_length + 1

A path passing through node can use both arrows:

answer = max(answer, left_arrow + right_arrow)

But the value returned upward can use only one side:

return max(left_arrow, right_arrow)

Testing

def run_tests():
    # Helper constructors are omitted on LeetCode.
    #
    # Example 1:
    #       5
    #      / \
    #     4   5
    #    / \   \
    #   1   1   5
    #
    # Expected: 2

    # Example 2:
    #       1
    #      / \
    #     4   5
    #    / \   \
    #   4   4   5
    #
    # Expected: 2

    # Empty tree:
    # root = None
    # Expected: 0

    # Single node:
    # root = TreeNode(1)
    # Expected: 0

    # All same values in a chain of 4 nodes:
    # 1 -> 1 -> 1 -> 1
    # Expected: 3

    pass

Test meaning: