Binary Tree Longest Consecutive Sequence - Practice Coding Problems

Binary Tree Longest Consecutive Sequence - 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.

The path must be from parent to child (cannot go upward in paths).

Input & Output

Example 1 — Basic Tree

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

› Output: 3

💡 Note: Longest consecutive sequence path is 3-4-5, so return 3. The path goes: 3→4→5.

Example 2 — No Long Sequence

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

› Output: 2

💡 Note: Longest consecutive sequence path is 2-3, so return 2. Note that 3-2-1 is not a valid path since we must go from parent to child.

Example 3 — Single Node

$ Input: root = [1]

› Output: 1

💡 Note: Single node forms a sequence of length 1.

Constraints

The number of nodes in the tree is in the range [1, 3 × 10⁴]
-3 × 10⁴ ≤ Node.val ≤ 3 × 10⁴

Visualization

Tap to expand

Understanding the Visualization

Input Tree

Binary tree with various integer values

Find Consecutive Paths

Look for paths where each child = parent + 1

Return Maximum Length

Length of longest consecutive sequence found

Key Takeaway

🎯 Key Insight: Use DFS to traverse the tree once, checking if each node continues the consecutive sequence from its parent (value = parent + 1)

Asked in

G Google 45 f Facebook 32 M Microsoft 28 a Amazon 25

The key insight is to use DFS traversal while tracking consecutive sequences. During traversal, check if each node's value equals parent's value + 1. If so, extend the current sequence; otherwise, start a new sequence. Track the maximum sequence length found. Best approach is optimized DFS with Time: O(n), Space: O(h).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Check All Paths	O(n²)	O(h)	Start DFS from every node and find the longest consecutive sequence
Optimized DFS	O(n)	O(h)	Single DFS pass tracking consecutive sequences while traversing

Brute Force - Check All Paths — Algorithm Steps

Visit every node as potential starting point
For each starting node, perform DFS to find longest consecutive path
Track maximum length found across all starting points

Visualization

Tap to expand

Step-by-Step Walkthrough

Get All Nodes

Collect every node as potential starting point

DFS From Each

Start consecutive sequence search from each node

Track Maximum

Keep the longest sequence found

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
};

struct TreeNode* createNode(int val) {
    struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    node->val = val;
    node->left = NULL;
    node->right = NULL;
    return node;
}

int dfsFromNode(struct TreeNode* node, int targetVal) {
    if (!node || node->val != targetVal) return 0;
    int leftLen = dfsFromNode(node->left, targetVal + 1);
    int rightLen = dfsFromNode(node->right, targetVal + 1);
    return 1 + (leftLen > rightLen ? leftLen : rightLen);
}

void getAllNodes(struct TreeNode* node, struct TreeNode** nodes, int* count) {
    if (!node) return;
    nodes[(*count)++] = node;
    getAllNodes(node->left, nodes, count);
    getAllNodes(node->right, nodes, count);
}

int solution(struct TreeNode* root) {
    if (!root) return 0;
    
    struct TreeNode* allNodes[1000];
    int count = 0;
    getAllNodes(root, allNodes, &count);
    
    int maxLength = 0;
    for (int i = 0; i < count; i++) {
        int length = dfsFromNode(allNodes[i], allNodes[i]->val);
        if (length > maxLength) {
            maxLength = length;
        }
    }
    
    return maxLength;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Simple parsing for [1,null,3,2,4,null,null,null,5]
    struct TreeNode* root = createNode(1);
    root->right = createNode(3);
    root->right->left = createNode(2);
    root->right->right = createNode(4);
    root->right->right->right = createNode(5);
    
    int result = solution(root);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

For each of n nodes, we potentially traverse the entire tree in worst case

⚠ Quadratic Growth

Space Complexity

O(h)

Recursion stack depth is limited by tree height h

✓ Linear Space

89.0K Views

Medium Frequency

~15 min Avg. Time

1.5K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Check All Paths — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler