# Longest Consecutive Sequence in Binary Tree

##### January 8, 2024

## Problem #

Given the root of a binary tree, find the length of the longest consecutive sequence path. The path refers to any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The longest consecutive path needs to be from parent to child (cannot be the reverse).

#### Example: #

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

Longest consecutive sequence path is `3-4-5`

, so return `3`

.

## Solution #

The problem can be solved using depth-first search (DFS). We will traverse the tree and at each node, we will pass down the current sequence length and the expected value if the sequence is to continue.

### Algorithm Steps: #

- Define a helper function that takes a node, its parent’s value, and the length of the current consecutive sequence.
- If the current node is
`None`

, return the length of the consecutive sequence. - If the current node’s value is one more than its parent’s value, increment the sequence length; otherwise, reset it to
`1`

. - Recursively call the helper function for the left and right child, and return the maximum of the current sequence length and the returned lengths from the children.

### Code in Python: #

```
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def longestConsecutive(root):
def dfs(node, parent_val, length):
if not node:
return length
length = length + 1 if node.val == parent_val + 1 else 1
left_length = dfs(node.left, node.val, length)
right_length = dfs(node.right, node.val, length)
return max(length, left_length, right_length)
if not root:
return 0
return dfs(root, root.val - 1, 0)
# Example Usage
root = TreeNode(1, None, TreeNode(3, TreeNode(2), TreeNode(4, None, TreeNode(5))))
print(longestConsecutive(root)) # Output: 3
```

### Time Complexity: #

O(N), where `N`

is the number of nodes in the tree. Each node is visited exactly once.

### Space Complexity: #

O(H), where `H`

is the height of the tree. This space is used for the recursion stack. In the worst case (a skewed tree), the space complexity could be O(N).

This problem showcases a practical use of DFS in a binary tree to solve a non-trivial problem related to node values and their relationships.