MediumTreeDepth-First SearchBinary Tree

Binary Tree Longest Consecutive Sequence

1 approach, code in every language

You are given the root of a binary tree. A consecutive sequence is a path that moves downward from a parent to a child where each step increases the value by exactly one.

The path must go strictly top-to-bottom (a node connects only to its child, never back up through a parent) and cannot skip or reverse direction. Return the length of the longest such consecutive-increasing path.

Example 1

Input: root = [1,null,3,2,4,null,null,null,5]

Output: 3

The longest consecutive path is 3 -> 4 -> 5, which has length 3.

Example 2

Input: root = [2,null,3,2,null,1]

Output: 2

2 -> 3 forms a consecutive increasing run of length 2; the 3 -> 2 -> 1 branch decreases, so it does not count.

Constraints

The number of nodes in the tree is in the range [1, 3 * 10^4].
-3 * 10^4 <= Node.val <= 3 * 10^4

Top-Down DFS Carrying the Current Run

Pass the expected next value and the current run length downward, extending or resetting at each node and tracking a global maximum.

Loading animation…

Intuition

Because a consecutive path only ever moves downward, we can decide how long the run is at a node using just its parent's value. As we descend we carry two pieces of information: the value the current node would need in order to continue the run, and the length of the run so far. If the node matches the expected value, the run grows by one; if it does not, the run restarts at length one beginning at this node. Every node updates a shared best, and both children are explored with the next expected value being node.val + 1. Visiting each node once with constant work per node makes this a clean linear-time solution.

Algorithm walkthrough

1Keep a shared best initialized to 0.
2Call dfs(root, root.val, 0) so the root matches its own expected value and starts a run of length 1.
3At each node, if node.val equals the expected target, increment length; otherwise reset length to 1.
4Update best = max(best, length).
5Recurse into left and right children with target = node.val + 1 and the current length.
6Return best once the traversal completes.

Implementation

class Solution:
    def longestConsecutive(self, root: Optional[TreeNode]) -> int:
        self.best = 0

        def dfs(node, target, length):
            if not node:
                return
            if node.val == target:
                length += 1
            else:
                length = 1
            self.best = max(self.best, length)
            dfs(node.left, node.val + 1, length)
            dfs(node.right, node.val + 1, length)

        if root:
            dfs(root, root.val, 0)
        return self.best

Time

O(n)

Space

O(h)

Every node is visited once with constant work; the recursion stack is O(h), ranging from O(log n) to O(n).

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Binary Trees & BST

After the pattern

Now solve one you haven't seen.

Reading a pattern isn't the same as using it. The practice set has 1,194 original problems on the same techniques, each graded in your browser.

Open the practice set Start the FDE path

1,194 problems · 15,062 graded tests · free