Path In Zigzag Labelled Binary Tree solution and explanation
9 more videos on this problem
Path in ZigZag labelled Binary tree || LeetcodePepcoding · 27:54 · 8K views
Path In Zigzag Labelled Binary Tree (Leetcode 1104)Coding Interviews · 14:36 · 2K views
Leetcode Weekly Contest 143 || Path In Zigzag Labelled Binary Tree || Code explainationcode Explainer · 8:57 · 2K views
Leetcode 1104 --path in zigzag labelled binary treeYou Wu · 12:00 · 593 views
米开：LeetCode 1104. Path In Zigzag Labelled Binary TreeM.C米开朗基罗 · 14:34 · 534 views
1104. Path In Zigzag Labelled Binary Tree (Leetcode Medium)Programming Live with Larry · 14:00 · 377 views
Path In Zigzag Labelled Binary Tree | Module : Trees | In Hindi | CPP | Video_49Pepcoding · 42:26 · 194 views
Leetcode 1104. Path In Zigzag Labelled Binary Tree (math symmetric)LetsCode · 7:29 · 110 views
Path In Zigzag Labelled Binary Tree | Module : Trees | In English | CPP | Video_49Pepcoding · 53:07 · 94 views
Path In Zigzag Labelled Binary Tree | Module : Trees | In English | Java | Video_49Pepcoding · 51:16 · 74 views
The 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.
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
Approach overview
Problem Overview: You are given a label in an infinite binary tree where levels alternate between left‑to‑right and right‑to‑left labeling. Level 1 starts normally (1), level 2 is reversed, level 3 is normal again, and so on. The task is to return the path from the root to the given label.
This problem looks like a regular tree traversal, but the zigzag labeling breaks the normal parent relationship. Instead of building the tree explicitly, the key idea is understanding how node labels map between normal and reversed levels.
Approach 1: Backtrack from the Given Label (O(log n) time, O(log n) space)
The optimal solution works directly with level math. First determine the level of the given label using log2(label). Each level has a range: [2^level, 2^(level+1)-1]. In zigzag levels, labels are mirrored compared to a normal binary tree. To move to the parent, convert the current label to its mirrored value within the level, divide by two to get the parent in a normal tree, then mirror again if needed. Repeating this process backtracks from the label to the root. Since the tree height grows logarithmically with the label value, the algorithm runs in O(log n) time with O(log n) space for storing the path.
The main insight: every zigzag level can be converted to its normal representation using the formula mirror = level_min + level_max - label. This allows you to reuse the standard parent calculation (parent = label / 2) while correcting for the reversed ordering.
Approach 2: Simulate the Tree and Compute the Path (O(n) time, O(n) space)
A more direct method is to simulate levels of the tree until the target label appears. Generate node values level by level while alternating between normal and reversed ordering. You can store each level in an array or queue, then track parent relationships as you build the structure. Once the target label is found, reconstruct the path by following stored parent references.
This approach is easier to reason about if you treat the structure as an explicit tree. However, it wastes memory and time because you generate many nodes that are never needed. For large labels, simulation becomes inefficient compared to the mathematical backtracking approach.
Recommended for interviews: The backtracking math approach is what interviewers typically expect. It shows you understand how binary tree levels work and how zigzag ordering changes the parent relationship. Implementing the simulation approach can demonstrate initial reasoning, but recognizing the mirror transformation and reducing the complexity to O(log n) shows stronger problem‑solving skills.
Approach 1: Approach 1: Backtrack from the Given Label
This approach involves figuring out the parent of the given label by calculating the position in the previous row of the binary tree. By continually moving upwards (to the parent), we can trace the path back to the root, adjusting for any inversions because of zigzag ordering.
def path_in_zigzag_tree(label):
path = []
while label:
path.append(label)
depth = label.bit_length() - 1
label = (2**depth + 2**(depth + 1) - 1 - label) // 2
return path[::-1]import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
class Solution {
public List<Integer> pathInZigZagTree(int label) {
List<Integer> path = new ArrayList<>();
while (label > 0) {
path.add(label);
int depth = (int)(Math.log(label) / Math.log(2));
label = (int)((Math.pow(2, depth) + Math.pow(2, depth + 1) - 1 - label) / 2);
}
Collections.reverse(path);
return path;
}
}#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
vector<int> pathInZigZagTree(int label) {
vector<int> path;
while (label > 0) {
path.push_back(label);
int depth = log2(label);
label = (pow(2, depth) + pow(2, depth + 1) - 1 - label) / 2;
}
reverse(path.begin(), path.end());
return path;
}function pathInZigZagTree(label) {
const path = [];
while (label > 0) {
path.push(label);
const depth = Math.floor(Math.log2(label));
label = Math.floor((2 ** depth + 2 ** (depth + 1) - 1 - label) / 2);
}
return path.reverse();
}using System;
using System.Collections.Generic;
public class Solution {
public IList<int> PathInZigZagTree(int label) {
var path = new List<int>();
while (label > 0) {
path.Add(label);
int depth = (int)Math.Log(label, 2);
label = (int)((Math.Pow(2, depth) + Math.Pow(2, depth + 1) - 1 - label) / 2);
}
path.Reverse();
return path;
}
}The solution in Python starts with initializing an empty list called path. We enter a loop that continues while the label is valid (truthy). In each iteration, we append the current label to the path. We calculate the depth of the current label using bit_length, which gives the length of the number in binary. The key transformation is to compute the next label as the parent during a zigzag, which is adjusted using the inversion formula: (2**depth + 2**(depth + 1) - 1 - label) // 2. Finally, we reverse the path list because we gathered labels from node to root.
The time complexity of this Python solution is O(log(label)) and the space complexity is also O(log(label)) due to storing the path in a list.
Approach 2: Approach 2: Simulate the Tree and Compute the Path
This approach involves simulating the binary tree's construction while computing each node's depth and its counterparts on the next and previous rows. As you reach the node matching the input label, you backtrack to collect the path.
def path_in_zigzag_tree(label):
def get_label(depth, idx):
if depth % 2 == 0:
return 2**depth - 1 - idx
else:
return 2**depth + idx
path = []
depth = label.bit_length() - 1
while depth >= 0:
path.append(label)
row_start = 2**depth
position = row_start - 1 if depth % 2 == 0 else label - row_start
parent_position = position // 2
depth -= 1
label = get_label(depth, parent_position)
return path[::-1]import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class Solution {
public List<Integer> pathInZigZagTree(int label) {
List<Integer> path = new ArrayList<>();
int depth = (int)(Math.log(label) / Math.log(2));
while (depth >= 0) {
path.add(label);
int rowStart = 1 << depth;
int position = depth % 2 == 0 ? (rowStart * 2 - 1 - label) : (label - rowStart);
int parentPosition = position / 2;
depth--;
label = getLabel(depth, parentPosition);
}
Collections.reverse(path);
return path;
}
private int getLabel(int depth, int idx) {
return depth % 2 == 0 ? ((1 << (depth + 1)) - 1) - idx : (1 << depth) + idx;
}
}#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
int getLabel(int depth, int idx) {
return depth % 2 == 0 ? ((1 << (depth + 1)) - 1) - idx : (1 << depth) + idx;
}
vector<int> pathInZigZagTree(int label) {
vector<int> path;
int depth = log2(label);
while (depth >= 0) {
path.push_back(label);
int row_start = 1 << depth;
int position = depth % 2 == 0 ? ((1 << (depth + 1)) - 1 - label) : (label - row_start);
int parent_position = position / 2;
--depth;
label = getLabel(depth, parent_position);
}
reverse(path.begin(), path.end());
return path;
}function pathInZigZagTree(label) {
const getLabel = (depth, idx) => {
return depth % 2 === 0 ? ((1 << (depth + 1)) - 1) - idx : (1 << depth) + idx;
};
const path = [];
let depth = Math.floor(Math.log2(label));
while (depth >= 0) {
path.push(label);
const rowStart = 1 << depth;
const position = depth % 2 === 0 ? ((1 << (depth + 1)) - 1 - label) : (label - rowStart);
const parentPosition = Math.floor(position / 2);
depth--;
label = getLabel(depth, parentPosition);
}
return path.reverse();
}using System;
using System.Collections.Generic;
public class Solution {
public IList<int> PathInZigZagTree(int label) {
var path = new List<int>();
int depth = (int)Math.Log2(label);
while (depth >= 0) {
path.Add(label);
int rowStart = 1 << depth;
int position = depth % 2 == 0 ? ((1 << (depth + 1)) - 1 - label) : (label - rowStart);
int parentPosition = position / 2;
depth--;
label = GetLabel(depth, parentPosition);
}
path.Reverse();
return path;
}
private int GetLabel(int depth, int idx) {
return depth % 2 == 0 ? ((1 << (depth + 1)) - 1) - idx : (1 << depth) + idx;
}
}In this Python solution, we define a helper function get_label to switch between label representations depending on depth parity. We calculate the starting position of each node and deduce the parent position while storing nodes into the path. After determining all involved nodes, we reverse the path to produce correct ordering.
The time complexity is O(log(label)) and the space complexity is also O(log(label)) due to path storage.
Approach 3: Mathematics
For a complete binary tree, the number of nodes in the ith row is 2^{i-1}, and the range of node labels in the ith row is [2^{i-1}, 2^i - 1]. In the problem, for odd-numbered rows, the nodes are labeled from left to right, while for even-numbered rows, the nodes are labeled from right to left. Therefore, for the node label in the ith row, its complementary node label is 2^{i-1} + 2^i - 1 - label. So the actual parent node label of node label is (2^{i-1} + 2^i - 1 - label) / 2. We can find the path from the root node to node label by continuously finding the complementary node label and the parent node label until we reach the root node.
Finally, we need to reverse the path, because the problem requires the path from the root node to node label.
The time complexity is O(log n), where n is the label of the node. Ignoring the space consumption of the answer, the space complexity is O(1).
func pathInZigZagTree(label int) (ans []int) {
x, i := 1, 1
for x<<1 <= label {
x <<= 1
i++
}
for ; i > 0; i-- {
ans = append(ans, label)
label = ((1 << (i - 1)) + (1 << i) - 1 - label) >> 1
}
for i, j := 0, len(ans)-1; i < j; i, j = i+1, j-1 {
ans[i], ans[j] = ans[j], ans[i]
}
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Backtrack from the Given Label | The time complexity of this Python solution is |
| Approach 2: Simulate the Tree and Compute the Path | The time complexity is |
| Mathematics | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Backtrack from the Given Label | O(log n) | O(log n) | Best solution for large labels; computes parents using level math without building the tree |
| Simulate the Tree and Compute the Path | O(n) | O(n) | Useful for understanding zigzag labeling or when explicitly modeling the tree structure |
Frequently asked questions
Is Path In Zigzag Labelled Binary Tree easy or hard?
The problem is rated Medium because the tree structure is simple but the zigzag labeling creates a non-obvious parent relationship. Once you recognize the mirror transformation between reversed and normal levels, the solution becomes a straightforward logarithmic backtracking process.
Path In Zigzag Labelled Binary Tree Python or Java solution?
In Python or Java, compute the node level using logarithms, then repeatedly transform the label using the mirror formula and divide by two to move to the parent. Append each label to a list and reverse it at the end. The implementation stays concise and runs in O(log n) time.
How to solve Path In Zigzag Labelled Binary Tree in O(log n)?
Determine the level of the label using logarithms. For each step toward the root, compute the mirrored value within that level using level_min + level_max - label. Convert to the parent by dividing by two, then continue until reaching the root. Reverse the collected nodes to produce the root-to-label path.
What is the best approach for Path In Zigzag Labelled Binary Tree?
The best approach is backtracking from the given label using level math and mirroring. Each level has a numeric range, and zigzag ordering can be converted to normal ordering using the formula level_min + level_max - label. After converting, the parent is simply label / 2. This method runs in O(log n) time and O(log n) space.
What data structure is used in Path In Zigzag Labelled Binary Tree?
The problem conceptually uses a binary tree, but the optimal solution avoids constructing the tree. Instead, it relies on mathematical properties of binary tree levels and stores the path in a list or array while backtracking from the label to the root.
What is the time complexity of Path In Zigzag Labelled Binary Tree?
The optimal solution runs in O(log n) time because you move from the given label up to the root, visiting one node per level. Since the height of a binary tree with label n is about log2(n), only logarithmic steps are required. Space complexity is also O(log n) for storing the path.
Is Path In Zigzag Labelled Binary Tree asked at Google, Amazon, or Meta?
This problem is a common medium-level tree and math question similar to those asked in interviews at companies like Amazon, Google, and Meta. It tests understanding of binary tree structure, level ranges, and mathematical transformations rather than pure traversal.