LeetCode 1104 - Path In Zigzag Labelled Binary Tree

This problem describes an infinite binary tree where nodes are normally arranged level by level, but with a twist in how labels are assigned. In a standard binary tree, nodes in each level are labeled from left to right.

leetcodemediummathtreebinary-tree

LeetCode Problem 1104

Difficulty: 🟡 Medium
Topics: Math, Tree, Binary Tree

Solution

Problem Understanding

This problem describes an infinite binary tree where nodes are normally arranged level by level, but with a twist in how labels are assigned. In a standard binary tree, nodes in each level are labeled from left to right. Here, the labeling alternates direction depending on the row number.

Odd numbered rows, such as row 1, row 3, and row 5, are labeled from left to right. Even numbered rows, such as row 2 and row 4, are labeled from right to left.

For example:

  • Row 1: 1
  • Row 2: 3, 2
  • Row 3: 4, 5, 6, 7
  • Row 4: 15, 14, 13, 12, 11, 10, 9, 8

The input is a single integer label, representing the value of a node somewhere in this zigzag labeled tree. The task is to return the full path from the root node (1) to that target node.

For example, if label = 14, the answer is [1, 3, 4, 14], because following parent relationships in the zigzag tree leads from node 14 to 4, then 3, and finally 1.

The constraint 1 <= label <= 10^6 tells us the tree depth is fairly small. Since each row doubles in size, even one million only reaches about 20 levels (2^20 ≈ 10^6). This strongly suggests that a logarithmic solution based on tree height is appropriate.

Several edge cases are important to recognize upfront. The smallest possible input is label = 1, which should return [1] immediately. Labels near row boundaries, such as powers of two, can be tricky because zigzag ordering flips exactly at row transitions. Another subtle case involves converting between zigzag labels and normal binary tree positions, since directly dividing by two does not always produce the correct parent in reversed rows.

Approaches

Brute Force Approach

A brute force solution would explicitly construct the tree level by level until reaching the target label. Since the tree alternates between left to right and right to left labeling, each level would need to be generated carefully.

After constructing enough of the tree to include the target node, we could maintain parent pointers while building the structure and reconstruct the path by tracing back from the target to the root.

This approach is correct because it simulates the exact structure described in the problem. Every node and parent relationship is explicitly represented.

However, this solution is inefficient and unnecessary. Since the tree grows exponentially, building all nodes up to 10^6 labels wastes both time and memory. We only need one path, not the whole tree.

Key Insight for the Optimal Approach

The key observation is that parent-child relationships in a complete binary tree are already well understood. The challenge is only the zigzag labeling.

If we temporarily convert a zigzag label into its equivalent label in a normal left to right binary tree, then finding the parent becomes easy using integer division by two.

For any row:

  • The minimum label is 2^(row-1)
  • The maximum label is 2^row - 1

If a row is reversed, a label can be mirrored into its normal position using:

$$\text{normal} = \text{rowMin} + \text{rowMax} - \text{zigzag}$$

Similarly, when moving upward to the parent, we can repeatedly mirror and divide by two.

Instead of constructing the tree, we simply work backward from the target node to the root, computing each parent mathematically.

Approach Time Complexity Space Complexity Notes
Brute Force O(label) O(label) Explicitly builds the tree and stores parent relationships
Optimal O(log label) O(log label) Walks upward through tree levels using mathematical transformations

Algorithm Walkthrough

  1. Determine the current row of the target label.

Since row r contains labels from 2^(r-1) to 2^r - 1, we repeatedly double until finding the row containing label. 2. Initialize an empty result list.

We will build the path from the target node upward to the root, then reverse it at the end. 3. Add the current label to the result.

At every step, the current node belongs to the path from root to target. 4. Compute the mirrored label in the current row.

Since zigzag rows alternate direction, we calculate the equivalent label in a normal binary tree:

$$mirrored = rowMin + rowMax - label$$

This gives the label's logical position in a standard left to right tree. 5. Find the parent in the normal tree.

Once mirrored, the parent is simply:

$$parent = mirrored // 2$$ 6. Move to the previous row.

After finding the parent, decrement the row number and repeat until reaching the root. 7. Reverse the collected path.

Since we built the path bottom up, reversing gives the required root to target order.

Why it works

The important invariant is that at every step, we correctly map the zigzag label into its equivalent position in a standard binary tree before computing the parent. Since binary tree parent relationships are deterministic (node // 2), and the mirroring transformation preserves structural position within a row, every computed ancestor is correct. Repeating this process eventually reaches the root, producing the exact path.

Python Solution

from typing import List

class Solution:
    def pathInZigZagTree(self, label: int) -> List[int]:
        path = []

        # Find the row containing the label
        row = 1
        while (1 << row) <= label:
            row += 1

        current = label

        while current >= 1:
            path.append(current)

            row_min = 1 << (row - 1)
            row_max = (1 << row) - 1

            # Mirror the current label into normal ordering
            mirrored = row_min + row_max - current

            # Move to parent
            current = mirrored // 2
            row -= 1

        return path[::-1]

The implementation first determines which row contains the target label. Since rows double in size, powers of two make this computation simple with bit shifting.

Next, the algorithm repeatedly moves upward toward the root. During each iteration, the current label is added to the path. The row boundaries are calculated using powers of two, which lets us determine the mirrored label in a normal binary tree arrangement.

After mirroring, integer division by two gives the parent node. The loop continues until reaching the root. Since the path is collected from target to root, reversing the list at the end produces the correct order.

Go Solution

func pathInZigZagTree(label int) []int {
	path := []int{}

	// Find row containing label
	row := 1
	for (1 << row) <= label {
		row++
	}

	current := label

	for current >= 1 {
		path = append(path, current)

		rowMin := 1 << (row - 1)
		rowMax := (1 << row) - 1

		// Mirror into normal ordering
		mirrored := rowMin + rowMax - current

		// Move to parent
		current = mirrored / 2
		row--
	}

	// Reverse path
	left, right := 0, len(path)-1
	for left < right {
		path[left], path[right] = path[right], path[left]
		left++
		right--
	}

	return path
}

The Go implementation follows exactly the same logic as the Python version. Since Go does not provide a built in reverse function for slices, the result slice is reversed manually using a two pointer swap.

Integer arithmetic is safe here because the maximum label is only 10^6, far below integer overflow limits. An empty slice is never returned because the problem guarantees label >= 1.

Worked Examples

Example 1

Input: label = 14

First determine the row:

Row Range Contains 14?
1 1 to 1 No
2 2 to 3 No
3 4 to 7 No
4 8 to 15 Yes

Now trace upward:

Step Current Row Row Min Row Max Mirrored Parent Path
1 14 4 8 15 9 4 [14]
2 4 3 4 7 7 3 [14, 4]
3 3 2 2 3 2 1 [14, 4, 3]
4 1 1 1 1 1 0 [14, 4, 3, 1]

Reverse the path:

[1, 3, 4, 14]

Example 2

Input: label = 26

Determine the row:

Row Range Contains 26?
1 1 to 1 No
2 2 to 3 No
3 4 to 7 No
4 8 to 15 No
5 16 to 31 Yes

Trace upward:

Step Current Row Row Min Row Max Mirrored Parent Path
1 26 5 16 31 21 10 [26]
2 10 4 8 15 13 6 [26, 10]
3 6 3 4 7 5 2 [26, 10, 6]
4 2 2 2 3 3 1 [26, 10, 6, 2]
5 1 1 1 1 1 0 [26, 10, 6, 2, 1]

Reverse the path:

[1, 2, 6, 10, 26]

Complexity Analysis

Measure Complexity Explanation
Time O(log label) We move up one tree level per iteration
Space O(log label) The output path stores one node per level

Since each row doubles in size, the tree height is logarithmic relative to the label value. At each level, only constant time arithmetic operations are performed. The path itself contains one node per row, so storage also grows logarithmically.

Test Cases

from typing import List

class Solution:
    def pathInZigZagTree(self, label: int) -> List[int]:
        path = []

        row = 1
        while (1 << row) <= label:
            row += 1

        current = label

        while current >= 1:
            path.append(current)

            row_min = 1 << (row - 1)
            row_max = (1 << row) - 1

            mirrored = row_min + row_max - current
            current = mirrored // 2
            row -= 1

        return path[::-1]

solution = Solution()

assert solution.pathInZigZagTree(14) == [1, 3, 4, 14]  # Example 1
assert solution.pathInZigZagTree(26) == [1, 2, 6, 10, 26]  # Example 2
assert solution.pathInZigZagTree(1) == [1]  # Root node
assert solution.pathInZigZagTree(2) == [1, 2]  # First reversed row
assert solution.pathInZigZagTree(3) == [1, 3]  # Other node in row 2
assert solution.pathInZigZagTree(4) == [1, 3, 4]  # First node in row 3
assert solution.pathInZigZagTree(7) == [1, 2, 7]  # Last node in row 3
assert solution.pathInZigZagTree(8) == [1, 2, 7, 8]  # Row boundary
assert solution.pathInZigZagTree(15) == [1, 3, 4, 15]  # End of reversed row
assert solution.pathInZigZagTree(16) == [1, 3, 4, 15, 16]  # Start of next row
assert solution.pathInZigZagTree(1000000)  # Large input stress test
Test Why
14 Verifies first provided example
26 Verifies second provided example
1 Tests smallest valid input
2 Tests beginning of reversed row
3 Tests end of reversed row
4 Tests transition into normal row
7 Tests last node of row 3
8 Tests row boundary transition
15 Tests end of reversed row
16 Tests start of next row
1000000 Stress test near constraint limit

Edge Cases

The Root Node (label = 1)

This is the smallest possible input and represents a tree with only the root in the path. A buggy implementation might incorrectly attempt parent calculations and produce extra values. This implementation handles it naturally because the loop runs once, appends 1, computes parent 0, and terminates.

Labels at Row Boundaries

Values like 8, 15, and 16 sit exactly at row boundaries where labeling direction changes. These are common sources of off by one errors because row minimums and maximums are computed differently at transitions. By explicitly calculating row_min = 2^(row-1) and row_max = 2^row - 1, the implementation consistently handles boundaries correctly.

Reversed Rows

Even numbered rows are labeled in reverse order, meaning a naive label // 2 parent calculation will fail. For example, node 14 does not have parent 7. Instead, it must first be mirrored to its standard binary tree position. The implementation avoids this bug by always converting to the mirrored value before computing the parent.