# LeetCode 298: Binary Tree Longest Consecutive Sequence

## Problem Restatement

We are given the root of a binary tree.

We need to return the length of the longest consecutive sequence path.

A consecutive path means each next node has value exactly one greater than its parent.

For example:

```python
3 -> 4 -> 5
```

is valid.

But:

```python
3 -> 2 -> 1
```

is not valid, because the values decrease.

The path can start at any node, but it must go downward from parent to child. We cannot go from a child back to its parent. The constraints say the tree has at least one node and at most `3 * 10^4` nodes.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Root of a binary tree |
| Output | Length of the longest consecutive downward path |
| Valid step | `child.val == parent.val + 1` |
| Direction | Parent to child only |
| Path start | Any node |

Function shape:

```python
class Solution:
    def longestConsecutive(self, root: TreeNode) -> int:
        ...
```

## Examples

For:

```python
root = [1, None, 3, 2, 4, None, None, None, 5]
```

The tree is:

```python
    1
     \
      3
     / \
    2   4
         \
          5
```

The longest consecutive path is:

```python
3 -> 4 -> 5
```

So the answer is:

```python
3
```

For:

```python
root = [2, None, 3, 2, None, 1]
```

The tree is:

```python
    2
     \
      3
     /
    2
   /
  1
```

The path:

```python
2 -> 3
```

has length `2`.

The path:

```python
3 -> 2 -> 1
```

does not count because it decreases. So the answer is:

```python
2
```

These examples match the source statement.

## First Thought: Check Every Starting Node

A direct approach is to try every node as the start of a path.

From each node, we follow children whose value is exactly one greater.

Then we keep the maximum length found.

This is correct, but it can repeat work. A subtree may be explored many times from different ancestors.

We can compute the answer in one DFS instead.

## Key Insight

During DFS, carry the length of the current consecutive path.

When we visit a child, compare it with its parent:

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

If this is true, the child continues the current path.

If this is false, the child starts a new path of length `1`.

So each node only needs two pieces of information from its parent:

| Value | Meaning |
|---|---|
| `parent_value` | The value needed to test consecutiveness |
| `length` | Current path length ending at the parent |

We update a global answer with the best length seen anywhere.

## Algorithm

Use DFS.

At each node:

1. If the node continues the sequence from its parent, increment the length.
2. Otherwise, reset the length to `1`.
3. Update the answer.
4. Recurse into the left child.
5. Recurse into the right child.

The path may start at any node because whenever a node does not continue its parent, we reset the length to `1`.

## Correctness

At each node, the DFS stores the length of the longest valid consecutive path that ends at that node and follows the current root-to-node traversal path.

If the node value is exactly one more than the parent value, then the current node extends the previous valid path, so increasing the length by one is correct.

If the node value does not continue the parent, then no valid consecutive path ending at this node can include the parent. The best path ending here starts at this node, so its length is `1`.

The algorithm updates the global answer at every node. Since every valid downward consecutive path ends at some node, that path length is considered when DFS visits its final node.

Therefore, after all nodes are visited, the global answer is the longest consecutive downward path in the whole tree.

## Complexity

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

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

For a balanced tree, `h = O(log n)`.

For a skewed tree, `h = O(n)`.

## Implementation

```python
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

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

        def dfs(node, parent_value, length):
            nonlocal answer

            if node is None:
                return

            if node.val == parent_value + 1:
                length += 1
            else:
                length = 1

            answer = max(answer, length)

            dfs(node.left, node.val, length)
            dfs(node.right, node.val, length)

        dfs(root, root.val - 1, 0)

        return answer
```

## Code Explanation

We store the best length found so far:

```python
answer = 0
```

The DFS receives the current node, the parent value, and the length of the current path before this node:

```python
def dfs(node, parent_value, length):
```

If the current node is missing, there is nothing to process:

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

If the current node continues the sequence:

```python
if node.val == parent_value + 1:
    length += 1
```

we extend the path.

Otherwise:

```python
else:
    length = 1
```

the current node starts a new path.

Then we update the global best answer:

```python
answer = max(answer, length)
```

Finally, we recurse into both children:

```python
dfs(node.left, node.val, length)
dfs(node.right, node.val, length)
```

The initial call uses:

```python
dfs(root, root.val - 1, 0)
```

so the root always starts with length `1`.

## Testing

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

def test_longest_consecutive():
    s = Solution()

    root = TreeNode(1)
    root.right = TreeNode(3)
    root.right.left = TreeNode(2)
    root.right.right = TreeNode(4)
    root.right.right.right = TreeNode(5)

    assert s.longestConsecutive(root) == 3

    root = TreeNode(2)
    root.right = TreeNode(3)
    root.right.left = TreeNode(2)
    root.right.left.left = TreeNode(1)

    assert s.longestConsecutive(root) == 2

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

    root = TreeNode(1)
    root.left = TreeNode(2)
    root.left.left = TreeNode(3)
    root.left.left.left = TreeNode(4)

    assert s.longestConsecutive(root) == 4

    root = TreeNode(4)
    root.left = TreeNode(3)
    root.left.left = TreeNode(2)

    assert s.longestConsecutive(root) == 1

    print("all tests passed")

test_longest_consecutive()
```

Test meaning:

| Test | Why |
|---|---|
| `3 -> 4 -> 5` inside tree | Standard example |
| `2 -> 3`, then decreasing path | Confirms downward increasing rule |
| Single node | Minimum valid tree |
| Long left chain | Confirms path can follow any child side |
| Decreasing chain | Confirms decreasing values do not count |