Binary Tree Longest Consecutive Sequence II
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
root = [2,1,3]3Starting 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
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. By combining these values from the left and right children, the algorithm can compute the longest path passing through the current node efficiently. This approach avoids redundant computations and leverages the tree structure to propagate information bottom-up.
Optimal Approach
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. Update a global variable tracking the maximum path length as the sum inc_len + dec_len - 1 at each node. Return the global maximum after traversing the entire tree.
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).
Pattern Spotlight
DFS (Post-Order Traversal with State Propagation)
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.
Solution
| 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 |
Step-by-Step Solution
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.
Perform DFS to Compute Increasing and Decreasing Lengths
| 5 | def dfs(node): |
| 6 | nonlocal longest_path |
| 7 | if not node: |
| 8 | return (0, 0) |
| 10 | inc_len = dec_len = 1 |
| 12 | for child in (node.left, node.right): |
| 13 | if not child: |
| 14 | continue |
| 16 | child_inc, child_dec = dfs(child) |
| 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) |
| 23 | longest_path = max(longest_path, inc_len + dec_len - 1) |
| 25 | return (inc_len, dec_len) |
Objective
To recursively compute the longest increasing and decreasing consecutive sequences starting from each node.
Key Insight
By performing a post-order DFS, the algorithm gathers information from the children before computing the current node's values. Comparing child values to the current node's value determines whether to extend an increasing or decreasing sequence. This bottom-up approach efficiently aggregates the necessary state to compute the longest path.
Interview Quick-Check
Core Logic
The DFS returns a tuple (inc_len, dec_len) representing the longest increasing and decreasing sequences starting at the current node, enabling the combination of child results.
State & Boundaries
The base case returns (0, 0) for null nodes, ensuring leaf nodes start with length 1 sequences.
Common Pitfalls & Bugs
Forgetting to handle null children or incorrectly updating inc_len and dec_len based on child values can lead to incorrect path lengths.
Update Global Longest Path Using Combined Sequences
| 23 | longest_path = max(longest_path, inc_len + dec_len - 1) |
Objective
To update the global longest path by combining the increasing and decreasing sequences from the current node's children.
Key Insight
The longest path passing through the current node can be formed by joining the longest increasing sequence from one child and the longest decreasing sequence from the other child, minus one to avoid double counting the current node. Updating the global maximum at each node ensures the final answer reflects the longest such path anywhere in the tree.
Interview Quick-Check
Core Logic
The global longest path is updated as max(longest_path, inc_len + dec_len - 1), capturing paths that increase then decrease or vice versa.
Common Pitfalls & Bugs
Failing to subtract one leads to overcounting the current node twice, inflating the path length.
Return Final Longest Consecutive Path Length
| 27 | dfs(root) |
| 28 | return longest_path |
Objective
To return the maximum length of the longest consecutive path found after DFS traversal completes.
Key Insight
After the DFS completes, the global variable holds the maximum path length found anywhere in the tree. Returning this value provides the final answer to the problem.
Interview Quick-Check
Core Logic
Returning the global longest_path variable after DFS ensures the result reflects the entire tree's longest consecutive path.
Line Analysis
This solution has 4 Critical lines interviewers watch for.
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.
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.
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.
dec_len = max(dec_len, child_dec + 1)Update decreasing length if child's sequence extends it.
This update is essential to correctly track the longest decreasing sequence, enabling the combination of increasing and decreasing sequences for the final path length.
longest_path = 0Initialize a variable to track the longest consecutive path found.
This variable acts as a global accumulator that is updated during DFS traversal to record the maximum path length encountered, enabling efficient retrieval after recursion.
if not node:Return (0, 0) for null nodes as base case.
Null nodes represent leaves' children and contribute no length; returning zeros ensures leaf nodes start with length 1 sequences when combined.
inc_len = dec_len = 1Initialize increasing and decreasing lengths to 1 for the current node.
Each node alone forms a consecutive sequence of length 1, serving as the base length before considering children.
if child.val == node.val + 1:Check if child's value is one greater than current node's value.
This condition identifies an increasing consecutive sequence from the current node to the child, allowing extension of the increasing length.
elif child.val == node.val - 1:Check if child's value is one less than current node's value.
This condition detects a decreasing consecutive sequence from the current node to the child, allowing extension of the decreasing length.
return (inc_len, dec_len)Return the increasing and decreasing lengths for the current node.
Returning these lengths allows the parent node to use this information to compute its own sequences, enabling the bottom-up aggregation of path lengths.
return longest_pathReturn the maximum longest consecutive path found.
After DFS completes, this returns the global maximum path length as the final answer to the problem.
nonlocal longest_pathDeclare longest_path as nonlocal to allow updates within DFS.
This declaration enables the DFS function to modify the outer scope variable, ensuring the global maximum path length is updated correctly during recursion.
return (0, 0)Base case return for null node.
This line terminates recursion for null nodes, preventing further calls and enabling correct sequence length calculations.
if not child:Skip processing if the child is null.
Null children do not contribute to sequences and must be skipped to avoid errors and unnecessary recursion.
dfs(root)Start DFS traversal from the root node.
This initiates the recursive process that computes the longest consecutive sequences for the entire tree.
def dfs(node):Define the DFS helper function to compute consecutive sequences.
Encapsulating the recursive logic in a helper function allows clean state management and facilitates bottom-up computation of increasing and decreasing sequences.
for child in (node.left, node.right):Iterate over the left and right children of the current node.
Exploring both children allows the algorithm to gather sequence information from all possible paths extending from the current node.
continueContinue to next iteration if child is null.
This control flow prevents null pointer errors and ensures only valid child nodes are processed.
Test Your Understanding
Why does the algorithm combine the increasing and decreasing lengths from children by summing them and subtracting one?
Because the longest consecutive path passing through a node can be formed by joining an increasing sequence from one child and a decreasing sequence from the other child through the node itself, but the node is counted in both sequences, so subtracting one avoids double counting.
Related Problems
DFS pattern
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