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^6Problem 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.
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.
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.
Python
C++
Java
JavaScript
C#
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.
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.
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.
Python
C++
Java
JavaScript
C#
The time complexity is O(log(label)) and the space complexity is also O(log(label)) due to path storage.
| 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 |
| 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 |
Path in ZigZag labelled Binary tree || Leetcode • Pepcoding • 8,427 views views
Watch 9 more video solutions →Practice Path In Zigzag Labelled Binary Tree with our built-in code editor and test cases.
Practice on FleetCode