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.
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
Input: label = 14
Output: [1,3,4,14]
Example 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
C++
#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
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
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
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
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
Rust
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
}
TypeScript
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.