Skip to main content
Talentd

Binary Tree Longest Consecutive Sequence - Solution & Explanation

MediumPremiumFree on FleetCodeTreeDepth-First SearchBinary Tree6 min readAsked at: Amazon, Meta, Google +1
Practice this problem

Problem Statement

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

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen 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

Video Solution

Binary Tree Longest Consecutive Sequence • Kevin Naughton Jr. • 39,034 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Binary Tree Longest Consecutive Sequence with our built-in code editor and test cases.

Practice on FleetCode
Previous

Binary Tree Longest Consecutive Sequence II

Next

Check if an Array Is Consecutive