Binary Tree Longest Consecutive Sequence - Solution & Explanation

Problem Overview: Given a binary tree, return the length of the longest path where each node value is exactly one greater than its parent. The sequence must follow parent-to-child direction only; it cannot change direction or skip nodes.

This problem focuses on recognizing patterns during tree traversal. At each node, you check whether the value continues a consecutive sequence from its parent. The goal is to track the longest such chain across the entire tree.

Approach 1: Start DFS from Every Node (Brute Force) (Time: O(n^2), Space: O(h))

A straightforward strategy is to treat every node as the start of a potential sequence. For each node, run a DFS and continue exploring children only if the child value equals node.val + 1. Track the length of that chain and update the global maximum. Because a DFS can run from every node and may visit many overlapping subtrees repeatedly, the worst-case time complexity becomes O(n^2) for skewed trees. Space complexity is O(h), where h is the tree height due to recursion stack.

Approach 2: Single DFS with Parent Tracking (Optimal) (Time: O(n), Space: O(h))

The optimal solution performs one depth-first search across the tree while carrying two pieces of state: the previous node value and the current consecutive length. When visiting a node, compare node.val with parent.val + 1. If it matches, extend the current sequence. Otherwise, reset the length to 1. Update a global maximum during traversal. Each node is processed exactly once, which gives O(n) time complexity.

This approach works well because consecutive validation only depends on the immediate parent. You don't need to recompute sequences starting from every node; the running length naturally propagates through recursion. The recursion depth determines memory usage, resulting in O(h) space where h is the height of the binary tree.

Implementation insight: Pass the expected next value or the parent value during recursion. When the condition breaks, reset the length and continue exploring children so new sequences can start from that node.

Recommended for interviews: Interviewers typically expect the single DFS solution with parent tracking. The brute-force method demonstrates understanding of tree traversal but wastes work by reprocessing subtrees. The optimized DFS shows that you recognize how sequence state can propagate during recursion, reducing the complexity to linear time.