Problem Description

You're given an infinite binary tree where every node has two children. The nodes are labeled in a special zigzag pattern by row:

• Odd-numbered rows (1st, 3rd, 5th, ...): Nodes are labeled from left to right
• Even-numbered rows (2nd, 4th, 6th, ...): Nodes are labeled from right to left

The labeling starts from 1 at the root and continues consecutively through each row. For example:

• Row 1: 1
• Row 2: 3, 2 (right to left)
• Row 3: 4, 5, 6, 7 (left to right)
• Row 4: 15, 14, 13, 12, 11, 10, 9, 8 (right to left)

Given a label of any node in this tree, you need to return an array containing all the node labels in the path from the root (node 1) to that target node.

For instance, if label = 14, the path from root would be [1, 3, 4, 14] because:

• Start at root node 1
• Go to node 3 in row 2
• Go to node 4 in row 3
• Reach target node 14 in row 4

The challenge is handling the zigzag labeling pattern - in even rows, the labels are reversed compared to a standard binary tree, so you need to account for this when finding parent-child relationships.

Intuition

The key insight is recognizing that in a standard binary tree (without zigzag labeling), finding the path from any node to the root is straightforward - we just repeatedly divide the label by 2 to get the parent. But the zigzag pattern complicates this.

Let's think about what happens with the zigzag pattern. In a normal binary tree, row i contains nodes labeled from 2^(i-1) to 2^i - 1. The zigzag doesn't change which nodes are in each row, it just reverses the labeling order in even rows.

For example, in row 4 (an even row), the nodes would normally be labeled 8, 9, 10, 11, 12, 13, 14, 15 from left to right. But with zigzag, they're labeled 15, 14, 13, 12, 11, 10, 9, 8 - completely reversed.

This means if we have a node with label 14 in row 4, its actual position in the tree structure corresponds to where node 9 would be in a normal tree. We can find this "mirror" or "complementary" label using the formula: start_of_row + end_of_row - label.

For row 4: 8 + 15 - 14 = 9

Once we know the actual structural position (9 in this case), we can find its parent in the normal way: 9 / 2 = 4. But wait - if the parent is in an odd row (row 3), its label is already correct. If the parent were in an even row, we'd need to apply the mirror transformation again.

So the algorithm becomes:

1. Find which row the current label is in
2. If it's in an even row, find its mirror position to get the "structural" position
3. Find the parent of that structural position
4. Store the current label and move up to the parent
5. Repeat until we reach the root

This builds the path from bottom to top, so we'll need to reverse it at the end to get the path from root to target.

Learn more about Tree, Math and Binary Tree patterns.

Solution Approach

Let's walk through the implementation step by step:

Step 1: Find the row number of the target label

First, we need to determine which row contains our target label. We use variables x and i:

• x tracks the starting label of each row (1, 2, 4, 8, 16, ...)
• i counts the row number

x = i = 1
while (x << 1) <= label:
    x <<= 1
    i += 1

We keep doubling x (left shift by 1) until 2*x > label. At this point, i tells us the row number containing label.

Step 2: Initialize the result array

We create an array of size i to store the path:

ans = [0] * i

Step 3: Build the path from bottom to top

Now we work backwards from the target label to the root:

while i:
    ans[i - 1] = label
    label = ((1 << (i - 1)) + (1 << i) - 1 - label) >> 1
    i -= 1

In each iteration:

1. Store the current label: ans[i - 1] = label places the current label at the correct position in our result array

2. Calculate the parent label: This is the trickiest part:

   • (1 << (i - 1)) gives us 2^(i-1), the start of row i
   • (1 << i) - 1 gives us 2^i - 1, the end of row i
   • So (1 << (i - 1)) + (1 << i) - 1 equals the sum of the first and last labels in row i

   The formula (start + end - label) gives us the "mirror" position of label in row i. This handles the zigzag pattern - if we're in an even row, this gives us the structural position; if we're in an odd row, it still works because the mirror of the mirror is the original position.

   Finally, >> 1 (right shift by 1) divides by 2 to get the parent's label.

3. Move up one row: i -= 1

Why this works:

The beauty of this approach is that the formula ((1 << (i - 1)) + (1 << i) - 1 - label) >> 1 automatically handles both odd and even rows correctly. When we apply the mirror transformation and then find the parent, we get the correct parent label regardless of whether the current row follows left-to-right or right-to-left labeling.

The path is built from the target node up to the root, with each label placed directly in its final position in the result array, so no reversal is needed at the end.

Example Walkthrough

Let's trace through finding the path to label 14.

Step 1: Find which row contains label 14

• Start with x = 1, i = 1 (row 1)
• x = 2, i = 2: Since 2 * 2 = 4 ≤ 14, continue
• x = 4, i = 3: Since 2 * 4 = 8 ≤ 14, continue
• x = 8, i = 4: Since 2 * 8 = 16 > 14, stop

Label 14 is in row 4.

Step 2: Create result array

• ans = [0, 0, 0, 0] (size 4 for 4 rows)

Step 3: Build path from bottom to top

Iteration 1 (row 4, i = 4):

• Store current label: ans[3] = 14 → ans = [0, 0, 0, 14]
• Calculate parent:
  • Row 4 range: 2^3 = 8 to 2^4 - 1 = 15
  • Mirror formula: (8 + 15 - 14) = 9
  • Parent: 9 / 2 = 4
• Move up: label = 4, i = 3

Iteration 2 (row 3, i = 3):

• Store current label: ans[2] = 4 → ans = [0, 0, 4, 14]
• Calculate parent:
  • Row 3 range: 2^2 = 4 to 2^3 - 1 = 7
  • Mirror formula: (4 + 7 - 4) = 7
  • Parent: 7 / 2 = 3
• Move up: label = 3, i = 2

Iteration 3 (row 2, i = 2):

• Store current label: ans[1] = 3 → ans = [0, 3, 4, 14]
• Calculate parent:
  • Row 2 range: 2^1 = 2 to 2^2 - 1 = 3
  • Mirror formula: (2 + 3 - 3) = 2
  • Parent: 2 / 2 = 1
• Move up: label = 1, i = 1

Iteration 4 (row 1, i = 1):

• Store current label: ans[0] = 1 → ans = [1, 3, 4, 14]
• i = 0, loop ends

Final result: [1, 3, 4, 14]

The path correctly shows: root (1) → node 3 in row 2 → node 4 in row 3 → target node 14 in row 4.

Solution Implementation

Time and Space Complexity

Time Complexity: O(log n), where n is the value of the label.

The algorithm consists of two main phases:

1. The first while loop finds the level i where the label exists by repeatedly doubling x until x * 2 > label. Since the tree is a complete binary tree and the label represents a node's value, this loop runs O(log n) times as it determines which level of the tree contains the label.

2. The second while loop traverses from the current node up to the root, performing constant-time operations at each level. Since there are i levels and i = O(log n), this loop also runs O(log n) times.

Each operation within both loops (bit shifting, arithmetic operations, array assignment) takes O(1) time. Therefore, the overall time complexity is O(log n).

Space Complexity: O(1) (excluding the output array)

The algorithm uses only a constant amount of extra space:

• Variables x and i are used to track the current level and power of 2
• The label variable is modified in place

The answer array ans has size O(log n), but following the reference answer's convention of ignoring the space consumption of the answer itself, the space complexity is O(1).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Parent Calculation Formula

One of the most common mistakes is getting the parent calculation formula wrong, especially when dealing with the zigzag pattern. Many developers try to handle odd and even rows separately with conditional logic, which leads to complex and error-prone code.

Incorrect approach:

# Wrong: Trying to handle odd/even rows separately
if level % 2 == 0:  # even row
    parent = (label + some_offset) // 2
else:  # odd row  
    parent = (label - some_offset) // 2

Why it fails: The relationship between parent and child in a zigzag tree isn't simply about adding or subtracting offsets based on row parity. The zigzag pattern requires finding the "structural position" of a node first.

Correct approach:

# Find the mirror position first, then get parent
level_start = 1 << (level - 1)
level_end = (1 << level) - 1
parent = (level_start + level_end - label) >> 1

2. Off-by-One Errors in Level Calculation

Another frequent mistake is incorrectly calculating which level (row) contains the target label, often resulting in off-by-one errors.

Incorrect approach:

# Wrong: May incorrectly identify the level
level = 0
while (1 << level) < label:  # Wrong comparison
    level += 1

Why it fails: This doesn't correctly identify when a label is at the boundary of a level. For example, if label = 4, this would incorrectly place it in level 3 instead of level 2.

Correct approach:

level_start = 1
level = 1
while (level_start << 1) <= label:  # Correct: check if next level's start > label
    level_start <<= 1
    level += 1

3. Forgetting to Handle the Root Level Specially

Some implementations fail when the target label is 1 (the root) because they don't handle the edge case where there's no parent to calculate.

Incorrect approach:

# Wrong: Doesn't handle root case properly
while label > 1:  # Stops before adding root to path
    path.append(label)
    label = calculate_parent(label)

Why it fails: This would miss adding the root (label 1) to the path.

Correct approach:

# Build path from bottom to top, naturally includes root
while level > 0:
    path[level - 1] = label
    if level > 1:  # Only calculate parent if not at root
        label = ((1 << (level - 1)) + (1 << level) - 1 - label) >> 1
    level -= 1

4. Building Path in Wrong Order

A subtle mistake is building the path in reverse order and forgetting to reverse it at the end, or incorrectly indexing when building directly.

Incorrect approach:

# Wrong: Appending without considering final order
path = []
while level > 0:
    path.append(label)  # This builds path from target to root
    # ... calculate parent
# Forgot to reverse: return path  # Wrong order!

Correct approach:

# Pre-allocate array and fill in correct positions
path = [0] * level
while level > 0:
    path[level - 1] = label  # Place at correct index
    # ... calculate parent
    level -= 1
return path  # Already in correct order