Binary Tree Longest Consecutive Sequence

Binary Tree Longest Consecutive Sequence

What is this problem about?

The Binary Tree Longest Consecutive Sequence coding problem asks you to find the length of the longest path in a binary tree where the values of the nodes increase by exactly one at each step along the path. Crucially, the path must follow a parent-child relationship (it must go downwards). This problem tests your ability to maintain state while traversing a tree and identify local vs. global maximums.

Why is this asked in interviews?

Interviewers at TikTok, Amazon, and Walmart Labs ask this to evaluate your recursion skills and your ability to pass information "down" the tree. It’s a classic example of how to solve a problem by looking at a node and its relationship to its parent. It tests your ability to handle edge cases, such as trees with a single node or trees where no consecutive sequence exists.

Algorithmic pattern used

The Depth-First Search (DFS) interview pattern is the most effective here. As you traverse down the tree, you pass the current length of the consecutive sequence and the value of the parent node to the children. If a child's value is parent_value + 1, you increment the count; otherwise, you reset the count to 1. You keep track of a global maximum variable throughout the traversal.

Example explanation

Consider a tree: 1

    3
   / 
  2   4
       
        5

1. Start at root (1). Current length = 1.
2. Move to 3. Is 3 = 1 + 1? No. Reset length to 1.
3. Move from 3 to 2. Is 2 = 3 + 1? No. Length at 2 = 1.
4. Move from 3 to 4. Is 4 = 3 + 1? Yes! Increment length: 1 + 1 = 2.
5. Move from 4 to 5. Is 5 = 4 + 1? Yes! Increment length: 2 + 1 = 3. The longest consecutive sequence is [3, 4, 5], so the answer is 3.

Common mistakes candidates make

One common mistake is allowing paths to go "up" the tree or across siblings; the problem usually specifies parent-to-child paths. Another mistake is resetting the sequence incorrectly when a "break" occurs—forgetting that the current node itself starts a new sequence of length 1. Candidates also sometimes struggle with the difference between a "consecutive sequence" (values like 1, 2, 3) and an "increasing sequence" (values like 1, 5, 10).

Interview preparation tip

When solving DFS problems where you need a global maximum, you can either use a class-level variable or pass an object/array by reference. Practice both styles. Also, try to identify the "base case" early: what should the function return if it hits a null node? (Usually 0 or the current path length).