Problem

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

In the odd numbered rows (ie., the first, third, fifth,…), the labelling is left to right, while in the even numbered rows (second, fourth, sixth,…), the labelling is right to left.

flowchart TB;
    %% Simpler layout without subgraphs. Use squircle nodes (parentheses) and color odd/even levels differently.
    classDef odd fill:#fff3e6,stroke:#333,stroke-width:1px;
    classDef even fill:#e6f2ff,stroke:#333,stroke-width:1px;
    classDef rootLevel fill:#f8f9fa,stroke:#333,stroke-width:2px;

    %% Nodes (squircle parentheses for rounded appearance)
    n1("1"):::odd

	n3("3"):::even
    n2("2"):::even

    n4("4"):::odd
    n5("5"):::odd
    n6("6"):::odd
    n7("7"):::odd

    n8("8"):::even
    n9("9"):::even
    n10("10"):::even
    n11("11"):::even
    n12("12"):::even
    n13("13"):::even
    n14("14"):::even
    n15("15"):::even
    
    n16("..."):::odd
    
	l1("Odd levels")
	l2("Even levels")

    %% Connections (binary tree)
    n1 --- n3 & n2

    n3 --- n4 & n5
    n2 --- n6 & n7

    n4 --- n15 & n14
    n5 --- n13 & n12
    n6 --- n11 & n10
    n7 --- n9 & n8
    
    n12 ~~~ n16
    n11 ~~~ n16

    
    classDef odd fill:#fff7e6,stroke:#333,stroke-width:1px,rx:12,ry:12;
    classDef even fill:#e8f6ff,stroke:#333,stroke-width:1px,rx:12,ry:12;
    classDef oddLegend fill:#fff7e6,stroke:#333,stroke-width:1px;
    classDef evenLegend fill:#e8f6ff,stroke:#333,stroke-width:1px;
    
    %% Layout hints
    linkStyle default interpolate basis
    
    %% Legend
    subgraph Legend
        direction LR
        l1:::oddLegend
        l2:::evenLegend
    end

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.

Below is a compact Mermaid diagram (up to label 15) that mirrors the image above. The diagram is drawn upside-down (root at the top but edges flowing downward visually inverted), uses rounded/squircle-style nodes, and colors each level to differentiate them.

Examples

Example 1

1
2

Input: label = 14
Output: [1,3,4,14]

Example 2

1
2

Input: label = 26
Output: [1,2,6,10,26]

Constraints

  • 1 <= label <= 10^6

Solution

Method 1 - Reverse Zigzag Level Mapping (Backtrack from label)

Intuition

The path from the root to a node in a zigzag labelled binary tree can be found by reversing the zigzag mapping at each level. For each level, if the level is even, the label is reversed; otherwise, it’s normal. We can work backwards from the label to the root.

Approach

For each level, compute the range of labels. If the level is even, map the label to its normal position, then move to its parent. Repeat until reaching the root, then reverse the path.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
    vector<int> pathInZigZagTree(int label) {
        vector<int> path;
        int level = 0, l = label;
        while ((1 << level) <= label) ++level;
        while (label) {
            path.push_back(label);
            int start = 1 << (level-1), end = (1 << level) - 1;
            label = (start + end - label) / 2;
            --level;
        }
        reverse(path.begin(), path.end());
        return path;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

func pathInZigZagTree(label int) []int {
    path := []int{}
    l := label
    level := 0
    for (1 << level) <= label { level++ }
    for label > 0 {
        path = append(path, label)
        start, end := 1<<(level-1), (1<<level)-1
        label = (start + end - label) / 2
        level--
    }
    for i, j := 0, len(path)-1; i < j; i, j = i+1, j-1 {
        path[i], path[j] = path[j], path[i]
    }
    return path
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

import java.util.*;
class Solution {
    public List<Integer> pathInZigZagTree(int label) {
        List<Integer> path = new ArrayList<>();
        int level = 0, l = label;
        while ((1 << level) <= label) level++;
        while (label > 0) {
            path.add(label);
            int start = 1 << (level-1), end = (1 << level) - 1;
            label = (start + end - label) / 2;
            level--;
        }
        Collections.reverse(path);
        return path;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    fun pathInZigZagTree(label: Int): List<Int> {
        val path = mutableListOf<Int>()
        var l = label
        var level = 0
        while ((1 shl level) <= label) level++
        var cur = label
        var curLevel = level
        while (cur > 0) {
            path.add(cur)
            val start = 1 shl (curLevel-1)
            val end = (1 shl curLevel) - 1
            cur = (start + end - cur) / 2
            curLevel--
        }
        path.reverse()
        return path
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

from typing import List

class Solution:
    def pathInZigZagTree(self, label: int) -> List[int]:
        path: List[int] = []
        level = 0
        while (1 << level) <= label:
            level += 1
        cur = label
        while cur:
            path.append(cur)
            start, end = 1 << (level-1), (1 << level) - 1
            cur = (start + end - cur) // 2
            level -= 1
        path.reverse()
        return path
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

fn pathInZigZagTree(mut label: i32) -> Vec<i32> {
    let mut path: Vec<i32> = Vec::new();
    let mut level: i32 = 0;
    while (1 << level) <= label { level += 1; }
    while label > 0 {
        path.push(label);
        let start = 1 << (level-1);
        let end = (1 << level) - 1;
        label = (start + end - label) / 2;
        level -= 1;
    }
    path.reverse();
    path
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

function pathInZigZagTree(label: number): number[] {
    const path: number[] = [];
    let level = 0;
    while ((1 << level) <= label) level++;
    while (label > 0) {
        path.push(label);
        const start = 1 << (level-1), end = (1 << level) - 1;
        label = Math.floor((start + end - label) / 2);
        level--;
    }
    path.reverse();
    return path;
}

Complexity

  • ⏰ Time complexity: O(log label) – We visit each level from the node up to the root (number of levels is ~ log(label)).
  • 🧺 Space complexity: O(log label) – The path stores one value per level.