Binary Tree Longest Consecutive Sequence II solution and explanation
Google
6 more videos on this problem
549. Binary Tree Longest Consecutive Sequence II | English | MediumSimple Code - 단순코드 · 8:54 · 1K views
Leetcode 549. Binary Tree Longest Consecutive Sequence II. 中文Alina L · 15:08 · 1K views
549. Binary Tree Longest Consecutive Sequence II (Leetcode Medium)Programming Live with Larry · 11:17 · 718 views
549. Binary Tree Longest Consecutive Sequence II - Week 4/5 Leetcode December ChallengeProgramming Live with Larry · 9:23 · 297 views
Leetcode 549. Binary Tree Longest Consecutive Sequence II (tree)LetsCode · 7:54 · 187 views
549. Binary Tree Longest Consecutive Sequence II | Korean | MediumSimple Code - 단순코드 · 9:54 · 91 views
LeetCode 549: Binary Tree Longest Consecutive Sequence IIAlitaCode · 29:21 · 12 views
The problem
Given the root of a binary tree, return the length of the longest consecutive path in the tree.
A consecutive path is a path where the values of the consecutive nodes in the path differ by one. This path can be either increasing or decreasing.
- For example,
[1,2,3,4]and[4,3,2,1]are both considered valid, but the path[1,2,4,3]is not valid.
On the other hand, the path can be in the child-Parent-child order, where not necessarily be parent-child order.
Example 1:
Input: root = [1,2,3] Output: 2 Explanation: The longest consecutive path is [1, 2] or [2, 1].
Example 2:
Input: root = [2,1,3] Output: 3 Explanation: The longest consecutive path is [1, 2, 3] or [3, 2, 1].
Constraints:
- The number of nodes in the tree is in the range
[1, 3 * 104]. -3 * 104 <= Node.val <= 3 * 104
Approach overview
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.
Solution
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def longestConsecutive(self, root: TreeNode) -> int:
def dfs(root):
if root is None:
return [0, 0]
nonlocal ans
incr = decr = 1
i1, d1 = dfs(root.left)
i2, d2 = dfs(root.right)
if root.left:
if root.left.val + 1 == root.val:
incr = i1 + 1
if root.left.val - 1 == root.val:
decr = d1 + 1
if root.right:
if root.right.val + 1 == root.val:
incr = max(incr, i2 + 1)
if root.right.val - 1 == root.val:
decr = max(decr, d2 + 1)
ans = max(ans, incr + decr - 1)
return [incr, decr]
ans = 0
dfs(root)
return ans/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
private int ans;
public int longestConsecutive(TreeNode root) {
ans = 0;
dfs(root);
return ans;
}
private int[] dfs(TreeNode root) {
if (root == null) {
return new int[] {0, 0};
}
int incr = 1, decr = 1;
int[] left = dfs(root.left);
int[] right = dfs(root.right);
if (root.left != null) {
if (root.left.val + 1 == root.val) {
incr = left[0] + 1;
}
if (root.left.val - 1 == root.val) {
decr = left[1] + 1;
}
}
if (root.right != null) {
if (root.right.val + 1 == root.val) {
incr = Math.max(incr, right[0] + 1);
}
if (root.right.val - 1 == root.val) {
decr = Math.max(decr, right[1] + 1);
}
}
ans = Math.max(ans, incr + decr - 1);
return new int[] {incr, decr};
}
}/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int ans;
int longestConsecutive(TreeNode* root) {
ans = 0;
dfs(root);
return ans;
}
vector<int> dfs(TreeNode* root) {
if (!root) return {0, 0};
int incr = 1, decr = 1;
auto left = dfs(root->left);
auto right = dfs(root->right);
if (root->left) {
if (root->left->val + 1 == root->val) incr = left[0] + 1;
if (root->left->val - 1 == root->val) decr = left[1] + 1;
}
if (root->right) {
if (root->right->val + 1 == root->val) incr = max(incr, right[0] + 1);
if (root->right->val - 1 == root->val) decr = max(decr, right[1] + 1);
}
ans = max(ans, incr + decr - 1);
return {incr, decr};
}
};/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func longestConsecutive(root *TreeNode) int {
ans := 0
var dfs func(root *TreeNode) []int
dfs = func(root *TreeNode) []int {
if root == nil {
return []int{0, 0}
}
incr, decr := 1, 1
left := dfs(root.Left)
right := dfs(root.Right)
if root.Left != nil {
if root.Left.Val+1 == root.Val {
incr = left[0] + 1
}
if root.Left.Val-1 == root.Val {
decr = left[1] + 1
}
}
if root.Right != nil {
if root.Right.Val+1 == root.Val {
incr = max(incr, right[0]+1)
}
if root.Right.Val-1 == root.Val {
decr = max(decr, right[1]+1)
}
}
ans = max(ans, incr+decr-1)
return []int{incr, decr}
}
dfs(root)
return ans
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| DFS from Every Node (Brute Force) | O(n²) | O(h) | Useful for understanding the problem or small trees where repeated traversal cost is acceptable. |
| Postorder DFS with Increasing/Decreasing Tracking | O(n) | O(h) | Optimal solution for interviews and production. Processes each node once and combines child results efficiently. |
Frequently asked questions
Is Binary Tree Longest Consecutive Sequence II easy or hard?
Binary Tree Longest Consecutive Sequence II is generally rated Medium difficulty. The traversal itself is straightforward, but combining increasing and decreasing sequences at each node requires careful reasoning. Recognizing the postorder DFS pattern is the main challenge.
Binary Tree Longest Consecutive Sequence II Python/Java solution
Most implementations define a DFS helper that returns a pair of integers representing increasing and decreasing sequence lengths. During traversal, the algorithm updates these values based on child node comparisons and tracks a global maximum. The same logic works consistently across Python, Java, C++, and Go with O(n) time complexity.
How to solve Binary Tree Longest Consecutive Sequence II in O(n)?
Perform a postorder DFS and return two values from each node: the longest increasing path and the longest decreasing path starting there. Compare the node's value with its children to extend either sequence. Combine both lengths at the current node using inc + dec - 1 to update the global maximum. This single traversal ensures O(n) runtime.
What is the best approach for Binary Tree Longest Consecutive Sequence II?
The best approach uses a postorder depth-first search that tracks two values for every node: the longest increasing sequence and the longest decreasing sequence starting from that node. By combining results from the left and right children, the algorithm can form paths that go child → parent → child. This processes each node once, giving O(n) time complexity and O(h) recursion space.
Is Binary Tree Longest Consecutive Sequence II asked at Google/Amazon/Meta?
Tree DFS problems that combine results from child nodes frequently appear in interviews at companies like Google, Amazon, and Meta. Variants of longest path or consecutive sequence problems test recursion, tree traversal, and dynamic programming on trees. Understanding how to merge increasing and decreasing paths is the key interview skill here.
What data structure is used in Binary Tree Longest Consecutive Sequence II?
The core data structure is a binary tree. The solution relies on depth-first search with recursion and uses simple integer tracking for increasing and decreasing path lengths. No additional complex structures are required beyond the recursion stack.
What is the time complexity of Binary Tree Longest Consecutive Sequence II?
The optimal DFS solution runs in O(n) time because every node in the binary tree is visited exactly once. During each visit, constant work is done to compare node values with its children and update increasing and decreasing path lengths. Space complexity is O(h), where h is the tree height due to the recursion stack.