260. Binary Tree Longest Consecutive Sequence
Your function receives root, the root node of a binary tree. Return a single integer: the number of nodes on the longest consecutive path anywhere in the tree.
A consecutive path begins at any node and walks strictly downward, parent to child. Each step must land on a value exactly one greater than the value it came from — no skips, no repeats, no decreases. The path does not have to start at the root or end at a leaf, and a lone node already counts as a path of length 1.
Only downward movement is allowed: a path can never turn back up through a parent or hop between siblings.
Example 1:
Input: root = [1, null, 3, 2, 4, null, null, null, 5]
Output: 3
Explanation: The chain 3 → 4 → 5 climbs by one at every step and covers three nodes. The 2 under the 3 breaks the run immediately, so nothing longer exists.
Example 2:
Input: root = [2, null, 3, 2, null, 1]
Output: 2
Explanation: 2 → 3 at the top is a run of two. Below it the values fall (3's child is 2, whose child is 1), so no downward chain does better.
Constraints:
- 1 ≤ number of nodes ≤ 3 * 10⁴
- -3 * 10⁴ ≤ Node.val ≤ 3 * 10⁴
Hints:
Look at each parent→child edge in isolation: either the child's value is exactly parent + 1 (the run grows by one node) or it isn't (a fresh run of length 1 starts at the child).
You do not need a separate search from every node. One DFS that carries the current streak length into each child — streak + 1 on a consecutive edge, reset to 1 otherwise — visits each node once and a running maximum captures the answer in O(n).
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: root = [1, null, 3, 2, 4, null, null, null, 5]
Expected output: 3