Binary Tree Longest Consecutive Sequence solution and explanation
Google
9 more videos on this problem
Binary Tree Longest Consecutive SequenceKevin Naughton Jr. · 11:30 · 39K views
BINARY TREE LONGEST CONSECUTIVE SEQUENCE | LEETCODE # 298 | PYTHON DFS SOLUTIONCracking FAANG · 10:18 · 2K views
leetcode 298. Binary Tree Longest Consecutive Sequence. 中文Alina L · 6:39 · 665 views
Binary Tree Longest Consecutive Sequence - LeetCode 298 - JavaScriptAlgoJS · 7:30 · 410 views
Leetcode 298 python Binary Tree Longest Consecutive SequenceFLAGeek官方频道 · 5:41 · 314 views
298. Binary Tree Longest Consecutive Sequence - Week 3/5 Leetcode December ChallengeProgramming Live with Larry · 3:22 · 268 views
298. Binary Tree Longest Consecutive Sequence (Leetcode Medium)Programming Live with Larry · 7:29 · 210 views
298 Binary Tree Longest Consecutive SequenceDev_God · 7:02 · 141 views
Leetcode 298 C++ Binary Tree Longest Consecutive SequenceFLAGeek官方频道 · 5:39 · 141 views
leetcode 298. Binary Tree Longest Consecutive Sequence - RecursionCode-Yao · 8:49 · 45 views
The problem
Given the root of a binary tree, return the length of the longest consecutive sequence path.
A consecutive sequence path is a path where the values increase by one along the path.
Note that the path can start at any node in the tree, and you cannot go from a node to its parent in the path.
Example 1:
Input: root = [1,null,3,2,4,null,null,null,5] Output: 3 Explanation: Longest consecutive sequence path is 3-4-5, so return 3.
Example 2:
Input: root = [2,null,3,2,null,1] Output: 2 Explanation: Longest consecutive sequence path is 2-3, not 3-2-1, so return 2.
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 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.
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: Optional[TreeNode]) -> int:
def dfs(root: Optional[TreeNode]) -> int:
if root is None:
return 0
l = dfs(root.left) + 1
r = dfs(root.right) + 1
if root.left and root.left.val - root.val != 1:
l = 1
if root.right and root.right.val - root.val != 1:
r = 1
t = max(l, r)
nonlocal ans
ans = max(ans, t)
return t
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) {
dfs(root);
return ans;
}
private int dfs(TreeNode root) {
if (root == null) {
return 0;
}
int l = dfs(root.left) + 1;
int r = dfs(root.right) + 1;
if (root.left != null && root.left.val - root.val != 1) {
l = 1;
}
if (root.right != null && root.right.val - root.val != 1) {
r = 1;
}
int t = Math.max(l, r);
ans = Math.max(ans, t);
return t;
}
}/**
* 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 longestConsecutive(TreeNode* root) {
int ans = 0;
function<int(TreeNode*)> dfs = [&](TreeNode* root) {
if (!root) {
return 0;
}
int l = dfs(root->left) + 1;
int r = dfs(root->right) + 1;
if (root->left && root->left->val - root->val != 1) {
l = 1;
}
if (root->right && root->right->val - root->val != 1) {
r = 1;
}
int t = max(l, r);
ans = max(ans, t);
return t;
};
dfs(root);
return ans;
}
};/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function longestConsecutive(root: TreeNode | null): number {
let ans = 0;
const dfs = (root: TreeNode | null): number => {
if (root === null) {
return 0;
}
let l = dfs(root.left) + 1;
let r = dfs(root.right) + 1;
if (root.left && root.left.val - root.val !== 1) {
l = 1;
}
if (root.right && root.right.val - root.val !== 1) {
r = 1;
}
const t = Math.max(l, r);
ans = Math.max(ans, t);
return t;
};
dfs(root);
return ans;
}/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func longestConsecutive(root *TreeNode) (ans int) {
var dfs func(*TreeNode) int
dfs = func(root *TreeNode) int {
if root == nil {
return 0
}
l := dfs(root.Left) + 1
r := dfs(root.Right) + 1
if root.Left != nil && root.Left.Val-root.Val != 1 {
l = 1
}
if root.Right != nil && root.Right.Val-root.Val != 1 {
r = 1
}
t := max(l, r)
ans = max(ans, t)
return t
}
dfs(root)
return
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| DFS from Every Node (Brute Force) | O(n^2) | O(h) | Good for initial reasoning or when demonstrating basic DFS traversal logic |
| Single DFS with Parent Tracking (Optimal) | O(n) | O(h) | Best general solution; processes each node once and is expected in interviews |
Frequently asked questions
Is Binary Tree Longest Consecutive Sequence easy or hard?
Binary Tree Longest Consecutive Sequence is generally classified as a medium-level problem. The traversal itself is straightforward, but recognizing that the sequence length should propagate through recursion is the key insight.
Binary Tree Longest Consecutive Sequence Python/Java solution
Most implementations perform a recursive DFS function that receives the current node, parent value, and running length. The same logic works across Python, Java, C++, Go, and TypeScript because it only requires tree traversal and integer comparisons.
How to solve Binary Tree Longest Consecutive Sequence in O(n)?
Perform a DFS while passing the parent value and the current sequence length. If the current node equals parent + 1, increase the length; otherwise reset it to 1. Update a global maximum during traversal. Because each node is visited once, the algorithm runs in O(n) time.
What is the best approach for Binary Tree Longest Consecutive Sequence?
The best approach is a single depth-first search that tracks the parent value and current consecutive length. During traversal, compare the current node with its parent and extend the sequence if the value increases by one. This method visits each node once, giving O(n) time complexity and O(h) recursion space.
Is Binary Tree Longest Consecutive Sequence asked at Google/Amazon/Meta?
Binary tree traversal problems like this frequently appear in interviews at companies such as Google, Amazon, and Meta. Variations involving consecutive paths, longest paths, or value constraints are common during tree and DFS interview rounds.
What data structure is used in Binary Tree Longest Consecutive Sequence?
The problem uses a binary tree as the primary data structure and is typically solved using depth-first search recursion. The recursion stack implicitly stores traversal state such as parent value and current sequence length.
What is the time complexity of Binary Tree Longest Consecutive Sequence?
The optimal DFS solution runs in O(n) time because each node in the binary tree is processed exactly once. The recursion stack uses O(h) space where h is the height of the tree. A brute-force approach that starts a DFS from every node can degrade to O(n^2) time.