Binary Tree Longest Consecutive Sequence II

Binary Tree Longest Consecutive Sequence II - Problem

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.

The path can be in the child-Parent-child order, where not necessarily be parent-child order.

Input & Output

Example 1 — Path Through Root

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

› Output: 3

💡 Note: The longest consecutive path is 2→3→4 with length 3. This path goes through the right subtree.

Example 2 — Single Node

$ Input: root = [2]

› Output: 1

💡 Note: Tree has only one node, so the longest consecutive path has length 1.

Example 3 — No Consecutive Path

$ Input: root = [1,3,5]

› Output: 1

💡 Note: No consecutive path exists (values differ by more than 1), so return 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 node values

Find Paths

Identify all possible consecutive sequences

Return Length

Length of longest consecutive path

Key Takeaway

🎯 Key Insight: The longest consecutive path can pass through any node, combining increasing and decreasing sequences from its subtrees

Asked in

G Google 25 F Facebook 18 A Amazon 15

The key insight is that the longest consecutive path can pass through any node, combining increasing and decreasing sequences from both subtrees. Best approach is single-pass DFS that tracks both directions simultaneously. Time: O(n), Space: O(h)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force DFS from Every Node	O(n²)	O(n)	Start DFS from every node and find the longest consecutive path
Optimized Single Pass DFS	O(n)	O(h)	Single DFS traversal tracking increasing/decreasing paths from each node

Brute Force DFS from Every Node — Algorithm Steps

Iterate through all nodes in the tree
For each node, start DFS in both increasing and decreasing directions
Track the maximum path length found

Visualization

Tap to expand

Step-by-Step Walkthrough

Select Node

Pick a node as potential path center

DFS Both Directions

Search increasing and decreasing paths

Combine Results

Find best path through this node

Code -

solution.c — C

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

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

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

struct TreeNode* buildTree(int* arr, int size) {
    if (size == 0 || arr[0] == INT_MIN) return NULL;
    
    struct TreeNode* root = createNode(arr[0]);
    struct TreeNode** queue = malloc(size * sizeof(struct TreeNode*));
    int front = 0, rear = 0;
    
    queue[rear++] = root;
    int i = 1;
    
    while (front < rear && i < size) {
        struct TreeNode* node = queue[front++];
        
        if (i < size && arr[i] != INT_MIN) {
            node->left = createNode(arr[i]);
            queue[rear++] = node->left;
        }
        i++;
        
        if (i < size && arr[i] != INT_MIN) {
            node->right = createNode(arr[i]);
            queue[rear++] = node->right;
        }
        i++;
    }
    
    free(queue);
    return root;
}

int dfsFromNode(struct TreeNode* node, int parentVal, int increasing) {
    if (!node) return 0;
    
    if (increasing && node->val != parentVal + 1) return 0;
    if (!increasing && node->val != parentVal - 1) return 0;
    
    int leftLen = dfsFromNode(node->left, node->val, increasing);
    int rightLen = dfsFromNode(node->right, node->val, increasing);
    
    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(int* rootArray, int size) {
    if (size == 0) return 0;
    
    struct TreeNode* root = buildTree(rootArray, size);
    if (!root) return 0;
    
    struct TreeNode** allNodes = malloc(size * sizeof(struct TreeNode*));
    int nodeCount = 0;
    getAllNodes(root, allNodes, &nodeCount);
    
    int maxLen = 1;
    
    for (int j = 0; j < nodeCount; j++) {
        struct TreeNode* node = allNodes[j];
        
        int incLeft = dfsFromNode(node->left, node->val, 1);
        int incRight = dfsFromNode(node->right, node->val, 1);
        int decLeft = dfsFromNode(node->left, node->val, 0);
        int decRight = dfsFromNode(node->right, node->val, 0);
        
        int throughNode = 1 + ((incLeft + decRight) > (decLeft + incRight) ? 
                               (incLeft + decRight) : (decLeft + incRight));
        maxLen = maxLen > throughNode ? maxLen : throughNode;
    }
    
    free(allNodes);
    return maxLen;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int arr[1000];
    int size = 0;
    
    char* token = strtok(line, "[],\n ");
    while (token != NULL && size < 1000) {
        if (strcmp(token, "null") == 0) {
            arr[size++] = INT_MIN;
        } else {
            arr[size++] = atoi(token);
        }
        token = strtok(NULL, "[],\n ");
    }
    
    printf("%d\n", solution(arr, size));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

For each of n nodes, we potentially traverse the entire tree again

⚠ Quadratic Growth

Space Complexity

O(n)

Recursion call stack can go up to tree height, worst case O(n)

⚡ Linearithmic Space

32.0K Views

Medium Frequency

~25 min Avg. Time

845 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 DFS from Every Node — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler