Path In Zigzag Labelled Binary Tree - Practice Coding Problems

Path In Zigzag Labelled Binary Tree - Problem

In an infinite binary tree where every node has two children, the nodes are labelled in row order with a zigzag pattern.

In the odd numbered rows (1st, 3rd, 5th, ...), the labelling is left to right.

In the even numbered rows (2nd, 4th, 6th, ...), the labelling is right to left.

Given the label of a node in this tree, return the labels in the path from the root of the tree to the node with that label.

Input & Output

Example 1 — Target in Level 4

$ Input: label = 14

› Output: [1,3,4,14]

💡 Note: Node 14 is in level 4 (even level, right to left). Working backwards: 14 → parent 4 (level 3) → parent 3 (level 2) → parent 1 (root)

Example 2 — Target in Level 3

$ Input: label = 26

› Output: [1,2,6,26]

💡 Note: Node 26 is in level 5 (odd level, left to right). Path: 26 → parent 6 (level 4) → parent 2 (level 2) → parent 1 (root)

Example 3 — Root Node

$ Input: label = 1

› Output: [1]

💡 Note: Root node has no parents, so path contains only itself

Constraints

1 ≤ label ≤ 10⁶

Visualization

Tap to expand

Understanding the Visualization

Zigzag Tree Structure

Infinite binary tree with alternating left-right, right-left labeling per level

Find Target Node

Locate the target node in the appropriate level

Trace Path

Work backwards from target to root using parent relationships

Key Takeaway

🎯 Key Insight: Each level has predictable zigzag pattern allowing direct mathematical calculation of parent-child relationships

Asked in

F Facebook 15 M Microsoft 12 A Amazon 8

The key insight is that each level in the zigzag tree has a predictable pattern - odd levels go left-to-right, even levels go right-to-left. We can use mathematical formulas to directly calculate parent-child relationships without building the tree. Best approach uses mathematical level calculation in O(log n) time and O(log n) space.

Common Approaches

Approach	Time	Space	Notes
✓ Level-by-Level Tree Construction	O(n)	O(log n)	Build the zigzag tree level by level until we find the target node
Mathematical Level Calculation	O(log n)	O(log n)	Use mathematical formulas to directly calculate parent-child relationships in the zigzag tree

Level-by-Level Tree Construction — Algorithm Steps

Generate levels with zigzag pattern
Find target node's position
Trace path from root to target

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Levels

Create each level with alternating left-right, right-left pattern

Find Target

Locate the target node in the constructed tree

Trace Path

Follow parent pointers back to root

Code -

solution.c — C

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

int* solution(int label, int* returnSize) {
    if (label == 1) {
        int* result = (int*)malloc(sizeof(int));
        result[0] = 1;
        *returnSize = 1;
        return result;
    }
    
    // Find which level the label is on
    int level = 1;
    int levelStart = 1;
    while (levelStart * 2 > label || label >= levelStart * 2 + (1 << level)) {
        level++;
        levelStart = 1 << (level - 1);
    }
    
    int* path = (int*)malloc(level * sizeof(int));
    int current = label;
    int pathIndex = 0;
    
    // Work backwards from target to root
    for (int currLevel = level; currLevel > 0; currLevel--) {
        path[pathIndex++] = current;
        if (currLevel == 1) {
            break;
        }
        
        // Calculate parent
        levelStart = 1 << (currLevel - 1);
        int levelEnd = (1 << currLevel) - 1;
        
        int posInLevel;
        if (currLevel % 2 == 0) {  // Even level (right to left)
            posInLevel = levelEnd - current;
        } else {  // Odd level (left to right)
            posInLevel = current - levelStart;
        }
        
        int parentLevelStart = 1 << (currLevel - 2);
        int parentPos = posInLevel / 2;
        
        if ((currLevel - 1) % 2 == 0) {  // Parent level is even
            int parentLevelEnd = (1 << (currLevel - 1)) - 1;
            current = parentLevelEnd - parentPos;
        } else {  // Parent level is odd
            current = parentLevelStart + parentPos;
        }
    }
    
    // Reverse the path
    for (int i = 0; i < pathIndex / 2; i++) {
        int temp = path[i];
        path[i] = path[pathIndex - 1 - i];
        path[pathIndex - 1 - i] = temp;
    }
    
    *returnSize = pathIndex;
    return path;
}

int main() {
    int label;
    scanf("%d", &label);
    
    int returnSize;
    int* result = solution(label, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("%d", result[i]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Must generate all levels up to the target node, where n is the target label value

✓ Linear Growth

Space Complexity

O(log n)

Store the path from root to target, which has depth log n

⚡ Linearithmic Space

23.2K Views

Medium Frequency

~15 min Avg. Time

892 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

Level-by-Level Tree Construction — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler