Skip to main content
Talentd

Binary Tree Longest Consecutive Sequence II - Solution & Explanation

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

Problem Statement

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

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor ā†’

Detailed Complexity Analysis

ApproachTimeSpaceWhen 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 TrackingO(n)O(h)Optimal solution for interviews and production. Processes each node once and combines child results efficiently.

Video Solution

549. Binary Tree Longest Consecutive Sequence II | English | Medium ā€¢ Simple Code - ė‹Øģˆœģ½”ė“œ ā€¢ 1,767 views views

Watch 6 more video solutions ā†’

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.

Ready to solve this problem?

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

Practice on FleetCode
Previous

Binary Tree Longest Consecutive Sequence

Next

Check if an Array Is Consecutive