# 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

| Item | Meaning |
|---|---|
| Input | Root of a binary tree |
| Output | Length of the longest same-value path |
| Path length | Number of edges |
| Path location | Can appear anywhere in the tree |

Example function shape:

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

## Examples

Example 1:

```text
        5
       / \
      4   5
     / \   \
    1   1   5
```

The longest same-value path is:

```text
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:

```text
        1
       / \
      4   5
     / \   \
    4   4   5
```

The longest same-value path is:

```text
4 -> 4 -> 4
```

It has `2` edges.

Answer:

```python
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:

```text
      4
     / \
    4   4
```

The best path through the root uses both sides:

```text
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:

```text
parent -> root -> left
```

or:

```text
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:
   ```python id="p7qjyh"
   left_arrow = left_length + 1
   ```
   Otherwise:
   ```python id="s3w1nw"
   left_arrow = 0
   ```
4. Do the same for the right child.
5. A same-value path passing through the current node has length:
   ```python id="0mtuu2"
   left_arrow + right_arrow
   ```
6. Update the global answer.
7. Return:
   ```python id="ojb39w"
   max(left_arrow, right_arrow)
   ```

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

## Walkthrough

Consider:

```text
        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`:

| Side | Child value matches? | Returned branch |
|---|---:|---:|
| Left | Yes | `0 + 1 = 1` |
| Right | Yes | `0 + 1 = 1` |

The best path through this node is:

```text
1 + 1 = 2
```

So the answer becomes `2`.

This node returns:

```text
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:

```python
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.

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n)` | Each node is processed once |
| Space | `O(h)` | Recursion stack height |

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

## Implementation

```python
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:

```python
answer = 0
```

stores the best full path found anywhere in the tree.

The helper:

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

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

For a missing node:

```python
if node is None:
    return 0
```

there is no branch.

We first compute both child branches:

```python
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:

```python
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:

```python
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:

```python
answer = max(answer, left_arrow + right_arrow)
```

But the value returned upward can use only one side:

```python
return max(left_arrow, right_arrow)
```

## Testing

```python
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:

| Test | Expected | Why |
|---|---:|---|
| `[5,4,5,1,1,null,5]` | `2` | Official example |
| `[1,4,5,4,4,null,5]` | `2` | Official example |
| Empty tree | `0` | No edges |
| Single node | `0` | Path length counts edges |
| Chain of four equal values | `3` | Four nodes make three edges |
| Tree with mixed values | Depends on structure | Confirms value checks block invalid branches |