What pattern does Binary Tree Longest Consecutive Sequence II use?

The Pattern: DFS (Post-Order Traversal with State Propagation) The Heuristic: When a problem requires combining information from child nodes to compute a property at the parent, use a post-order DFS that returns state information upward, enabling efficient bottom-up aggregation without redundant recomputation.

Binary Tree Longest Consecutive Sequence II

Q: What is the time complexity of Binary Tree Longest Consecutive Sequence II?

O(n). Each node is visited exactly once during the DFS traversal, and constant work is done per node to compute and update the longest consecutive sequences.

Problem

Given the root of a binary tree, return the length of the longest consecutive path in the tree where the path can be either strictly increasing or strictly decreasing by 1 between adjacent nodes, and the path can change direction at most once (i.e., it can be a sequence that increases then decreases or vice versa).

The number of nodes in the tree is in the range [1, 3 * 10⁴]
−3 * 10⁴ ≤ Node.val ≤ 3 * 10⁴

Example

Input: root = [2,1,3]

Output: 3

Starting at node 1, the path 1 -> 2 -> 3 forms a consecutive increasing sequence of length 3. The DFS explores each node, calculating the longest increasing and decreasing sequences from its children. At node 2, the algorithm combines the increasing sequence from the right child (3) and the decreasing sequence from the left child (1) to find the longest path passing through 2, which is 3 nodes long.

Approach

Straightforward Solution

A brute-force approach might try all paths in the tree, checking if they are consecutive increasing or decreasing sequences, which is exponential in time and infeasible for large trees.

Core Observation

The longest consecutive path can be decomposed into two parts at any node: the longest increasing path starting from that node and the longest decreasing path starting from that node. The maximum path length passing through a node is the sum of these two lengths minus one (to avoid double counting the node).

Path to Optimal

Preview

The key insight is to use a post-order DFS traversal that returns, for each node, the length of the longest increasing and decreasing consecutive sequences starting from that node…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Perform a DFS that returns a tuple (inc_len, dec_len) representing the longest increasing and decreasing consecutive sequences starting at the current node. For each child, compare its value to the current node's value to update inc_len or dec_len accordingly…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(n)

Each node is visited exactly once during the DFS traversal, and constant work is done per node to compute and update the longest consecutive sequences.

Space

O(h)

The auxiliary space is proportional to the height of the tree due to the recursion stack. In the worst case (skewed tree), this can be O(n), but for balanced trees, it is O(log n).

Solution

Python

1class Solution:
2    def longestConsecutive(self, root: Optional[TreeNode]) -> int:
3         longest_path = 0
4
5        def dfs(node):
6            nonlocal longest_path
7            if not node:
8                return (0, 0)  
9
10            inc_len = dec_len = 1
11
12            for child in (node.left, node.right):
13                if not child:
14                    continue
15
16                child_inc, child_dec = dfs(child)
17
18                if child.val == node.val + 1:
19                    inc_len = max(inc_len, child_inc + 1)
20                elif child.val == node.val - 1:
21                    dec_len = max(dec_len, child_dec + 1)
22
23            longest_path = max(longest_path, inc_len + dec_len - 1)
24
25            return (inc_len, dec_len)
26
27        dfs(root)
28        return longest_path   

Step-by-Step Solution

1

Initialize Global Tracker for Longest Path

3	`longest_path = 0`

Objective

To maintain a global variable that tracks the maximum length of any consecutive path found during DFS traversal.

Key Insight

A global variable allows the DFS helper function to update the maximum path length found so far without needing to propagate this information up the recursion stack explicitly. This simplifies the logic and ensures the final answer is accessible after traversal.

Interview Quick-Check

Core Logic

Using a nonlocal or global variable to track the maximum path length allows the DFS to update the answer at each node efficiently.

State & Boundaries

The variable must be updated after processing each node's children to capture the longest path passing through that node.

2

Perform DFS to Compute Increasing and Decreasing Lengths

To recursively compute the longest increasing and decreasing consecutive sequences starting from each node.

3

Update Global Longest Path Using Combined Sequences

To update the global longest path by combining the increasing and decreasing sequences from the current node's children.

4

Return Final Longest Consecutive Path Length

To return the maximum length of the longest consecutive path found after DFS traversal completes.

3 more steps with full analysis available on Pro.

Line Analysis

This solution has 4 Critical lines interviewers watch for.

Line 23 Critical

longest_path = max(longest_path, inc_len + dec_len - 1)

Update the global longest path with combined increasing and decreasing lengths.

This line embodies the key insight that the longest consecutive path can be formed by joining increasing and decreasing sequences at a node, and subtracting one avoids double counting the node itself, making this the definitive step for correctness.

Line 16 Critical

child_inc, child_dec = dfs(child)

Recursively compute increasing and decreasing lengths for the child node.

This recursive call is the core of the bottom-up DFS approach, enabling the aggregation of sequence lengths from children to parent nodes, which is essential for computing the longest consecutive path.

Line 19 Critical

inc_len = max(inc_len, child_inc + 1)

Update increasing length if child's sequence extends it.

This update is critical because it extends the increasing sequence length by incorporating the child's sequence, enabling the algorithm to track the longest increasing path accurately.

Full line-by-line criticality + rationale for all 18 lines available on Pro.

Test Your Understanding

Why does the algorithm combine the increasing and decreasing lengths from children by summing them and subtracting one?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Binary Tree Longest Consecutive Sequence II from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Binary Tree Longest Consecutive Sequence II drill

or drill a free problem

1	`class Solution:`
2	`def longestConsecutive(self, root: Optional[TreeNode]) -> int:`
3	`longest_path = 0`
4
5	`def dfs(node):`
6	`nonlocal longest_path`
7	`if not node:`
8	`return (0, 0)`
9
10	`inc_len = dec_len = 1`
11
12	`for child in (node.left, node.right):`
13	`if not child:`
14	`continue`
15
16	`child_inc, child_dec = dfs(child)`
17
18	`if child.val == node.val + 1:`
19	`inc_len = max(inc_len, child_inc + 1)`
20	`elif child.val == node.val - 1:`
21	`dec_len = max(dec_len, child_dec + 1)`
22
23	`longest_path = max(longest_path, inc_len + dec_len - 1)`
24
25	`return (inc_len, dec_len)`
26
27	`dfs(root)`
28	`return longest_path`