Watch 10 video solutions for Path In Zigzag Labelled Binary Tree, a medium level problem involving Math, Tree, Binary Tree. This walkthrough by Pepcoding has 8,427 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |