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.

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.

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

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

C++
 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;
    }
};
Go
 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
}
Java
 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;
    }
}
Kotlin
 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
    }
}
Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

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

fn path_in_zigzag_tree(mut label: i32) -> Vec<i32> {
    let mut path = vec![];
    let mut level = 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
}
TypeScript
 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)
  • 🧺 Space complexity: O(log label)