Path In Zigzag Labelled Binary Tree - Solution & Explanation
Problem Statement
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.
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.
Code
Python
C++
Java
JavaScript
C#
Complexity
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.
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.
Code
Python
C++
Java
JavaScript
C#
Complexity
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).
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 | — |
Detailed 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 |
Video Solution
Path in ZigZag labelled Binary tree || Leetcode • Pepcoding • 8,517 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Path In Zigzag Labelled Binary Tree easy or hard?
Path In Zigzag Labelled Binary Tree Python or Java solution?
How to solve Path In Zigzag Labelled Binary Tree in O(log n)?
What is the best approach for Path In Zigzag Labelled Binary Tree?
What data structure is used in Path In Zigzag Labelled Binary Tree?
What is the time complexity of Path In Zigzag Labelled Binary Tree?
Is Path In Zigzag Labelled Binary Tree asked at Google, Amazon, or Meta?
Ready to solve this problem?
Practice Path In Zigzag Labelled Binary Tree with our built-in code editor and test cases.
Practice on FleetCodeTable of Contents
Practice this problem
Open in Editor