# LeetCode 549: Binary Tree Longest Consecutive Sequence II

## Problem Restatement

We are given the root of a binary tree.

We need to find the length of the longest consecutive path.

A path can move from parent to child or child to parent, as long as the path stays connected.

The consecutive values may either:

- increase by `1`
- decrease by `1`

The path may change direction once at a node.

For example:

```text
1 - 2 - 3
```

is valid because values increase consecutively.

Also:

```text
3 - 2 - 1
```

is valid because values decrease consecutively.

Even:

```text
1 - 2 - 1
```

is valid as a connected path, but it is not strictly consecutive in one direction through the center according to the required rules.

The important detail is that the path does not need to start at the root.

The official problem allows increasing and decreasing consecutive sequences, and the path may go child-parent-child. ([leetcode.com](https://leetcode.com/problems/binary-tree-longest-consecutive-sequence-ii/?utm_source=chatgpt.com))

## Input and Output

| Item | Meaning |
|---|---|
| Input | Root of a binary tree |
| Output | Length of the longest consecutive path |
| Consecutive rule | Neighboring values differ by exactly `1` |
| Direction | Increasing or decreasing |
| Path shape | Can pass through a node |

Function shape:

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

## Examples

Consider:

```text
    2
   / \
  1   3
```

The path:

```text
1 -> 2 -> 3
```

is consecutive increasing.

The length is:

```python
3
```

So the answer is:

```python
3
```

Another example:

```text
      3
     / \
    2   4
   /
  1
```

One longest path is:

```text
1 -> 2 -> 3 -> 4
```

Length:

```python
4
```

Now consider:

```text
    2
   /
  3
```

The path:

```text
3 -> 2
```

is decreasing consecutive.

The answer is:

```python
2
```

## First Thought: Track Increasing Paths Only

A simpler related problem asks only for increasing sequences downward from parent to child.

But this problem is harder because:

1. The sequence may increase or decrease.
2. The path may pass through a node.
3. One side may decrease while the other side increases.

Example:

```text
1 -> 2 -> 3
```

At node `2`:

- left side contributes decreasing
- right side contributes increasing

So we need to combine information from both children.

## Key Insight

For every node, we need two values:

| Value | Meaning |
|---|---|
| `inc` | Longest increasing consecutive path starting at this node |
| `dec` | Longest decreasing consecutive path starting at this node |

Suppose we are at node `x`.

If:

```python
child.val == x.val + 1
```

then the child extends an increasing path.

If:

```python
child.val == x.val - 1
```

then the child extends a decreasing path.

The longest path through the current node can combine:

```text
decreasing side + current node + increasing side
```

For example:

```text
1 -> 2 -> 3
```

At node `2`:

- decreasing length from left = `2`
- increasing length from right = `2`

Combined path length:

```python
2 + 2 - 1 = 3
```

We subtract `1` because the current node is counted twice.

## Algorithm

Use DFS.

For each node:

1. Recursively compute `(inc, dec)` from the left child.
2. Recursively compute `(inc, dec)` from the right child.
3. Initialize:

```python
inc = 1
dec = 1
```

4. If a child continues an increasing sequence:
   - update `inc`
5. If a child continues a decreasing sequence:
   - update `dec`
6. Update the global answer using:

```python
inc + dec - 1
```

7. Return `(inc, dec)` for the current node.

## Correctness

For every node, the DFS computes:

- `inc`: the longest increasing consecutive path starting at that node and moving downward
- `dec`: the longest decreasing consecutive path starting at that node and moving downward

These values are correct by recursion.

Suppose a child value equals:

```python
node.val + 1
```

Then the child continues an increasing consecutive sequence from the current node. So the current node can extend the child's increasing path by one.

Similarly, if:

```python
child.val == node.val - 1
```

then the child continues a decreasing sequence from the current node.

The longest valid path passing through the current node combines one decreasing branch and one increasing branch. The current node connects those two directions.

The combined length is:

```python
inc + dec - 1
```

because the current node belongs to both paths and would otherwise be counted twice.

Every valid consecutive path in the tree has some highest turning node where the increasing and decreasing parts meet. When DFS processes that node, the algorithm evaluates the corresponding combined length.

Therefore, the global maximum found by the algorithm is the length of the longest consecutive path in the tree.

## Complexity

Let `n` be the number of nodes.

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

`h` is the height of the tree.

Worst case:

```python
O(n)
```

Balanced tree:

```python
O(log n)
```

## Implementation

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

from typing import Optional

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

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

            if node is None:
                return (0, 0)

            inc = 1
            dec = 1

            if node.left:
                left_inc, left_dec = dfs(node.left)

                if node.left.val == node.val + 1:
                    inc = max(inc, left_inc + 1)

                elif node.left.val == node.val - 1:
                    dec = max(dec, left_dec + 1)

            if node.right:
                right_inc, right_dec = dfs(node.right)

                if node.right.val == node.val + 1:
                    inc = max(inc, right_inc + 1)

                elif node.right.val == node.val - 1:
                    dec = max(dec, right_dec + 1)

            answer = max(answer, inc + dec - 1)

            return (inc, dec)

        dfs(root)
        return answer
```

## Code Explanation

For each node, we start with:

```python
inc = 1
dec = 1
```

A single node itself forms a path of length `1`.

Then we recursively process the left child:

```python
left_inc, left_dec = dfs(node.left)
```

If the left child is one larger:

```python
node.left.val == node.val + 1
```

then the current node extends an increasing path:

```python
inc = max(inc, left_inc + 1)
```

If the left child is one smaller:

```python
node.left.val == node.val - 1
```

then the current node extends a decreasing path:

```python
dec = max(dec, left_dec + 1)
```

The same logic applies to the right child.

Then we combine both directions:

```python
answer = max(answer, inc + dec - 1)
```

This checks the longest path passing through the current node.

Finally, we return:

```python
(inc, dec)
```

for use by the parent.

## Small Walkthrough

Tree:

```text
    2
   / \
  1   3
```

At node `1`:

```python
inc = 1
dec = 1
```

At node `3`:

```python
inc = 1
dec = 1
```

At node `2`:

Left child:

```python
1 == 2 - 1
```

So:

```python
dec = 2
```

Right child:

```python
3 == 2 + 1
```

So:

```python
inc = 2
```

Combined:

```python
2 + 2 - 1 = 3
```

Answer becomes:

```python
3
```

## Testing

```python
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def run_tests():
    s = Solution()

    root = TreeNode(2, TreeNode(1), TreeNode(3))
    assert s.longestConsecutive(root) == 3

    root = TreeNode(
        3,
        TreeNode(
            2,
            TreeNode(1),
            None,
        ),
        TreeNode(4),
    )
    assert s.longestConsecutive(root) == 4

    root = TreeNode(2, TreeNode(3))
    assert s.longestConsecutive(root) == 2

    root = TreeNode(1)
    assert s.longestConsecutive(root) == 1

    root = TreeNode(
        2,
        TreeNode(1),
        TreeNode(2),
    )
    assert s.longestConsecutive(root) == 2

    print("all tests passed")

run_tests()
```

| Test | Why |
|---|---|
| `1 -> 2 -> 3` | Basic increasing path |
| Longer mixed path | Checks combination through center |
| Decreasing pair | Checks decreasing logic |
| Single node | Minimum input |
| Duplicate value | Confirms equal values do not extend sequence |