Binary Tree Longest Consecutive Sequence II - Solution & Explanation

Problem Overview: Given a binary tree, return the length of the longest consecutive sequence path. The path can be either increasing or decreasing and can move from child → parent → child, but nodes must remain connected through parent-child relationships.

This variation is trickier than the original consecutive sequence problem because the path can change direction at a node. For example, 1-2-3 is valid (increasing) and 3-2-1 is valid (decreasing). Even a combined path like 1-2-3-2-1 can be formed by joining an increasing and decreasing sequence around the same node.

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

One straightforward strategy is to treat every node as a potential starting point and run a DFS that continues only if the next node forms a consecutive relationship (+1 or -1). For each node, recursively explore its children and track the longest increasing or decreasing chain. Since this DFS may traverse large portions of the tree repeatedly, the total runtime can degrade to O(n²) in skewed trees. Space usage is O(h) due to recursion depth, where h is the tree height. This approach is easy to reason about but inefficient for large trees.

Approach 2: Postorder DFS with Increasing/Decreasing Lengths (Optimal) (Time: O(n), Space: O(h))

The optimal solution performs a single postorder traversal of the binary tree. For each node, compute two values: the longest increasing sequence starting from this node and the longest decreasing sequence starting from this node. Recursively collect the same information from the left and right children.

When visiting a node, compare its value with each child. If child.val == node.val + 1, extend the increasing sequence. If child.val == node.val - 1, extend the decreasing sequence. Maintain the best lengths from both sides. The key insight is that a valid longest path may pass through the current node by combining a decreasing path from one child and an increasing path from the other.

At each node, compute inc (longest increasing) and dec (longest decreasing). Update the global answer using inc + dec - 1, which merges both directions with the current node as the pivot. Because each node is processed once during the DFS, the total runtime is O(n) with O(h) recursion stack space.

This technique is a classic pattern for problems on trees where information from children must be combined at the parent. It relies on depth-first search and postorder aggregation.

Recommended for interviews: The postorder DFS approach is the expected solution. Mentioning the brute force idea shows understanding of the problem space, but implementing the single-pass DFS that tracks increasing and decreasing chains demonstrates strong tree DP and DFS reasoning.