Path In Zigzag Labelled Binary Tree: Mirror Math

Given a complete binary tree where every row is labelled in alternating order (even rows left to right, odd rows right to left), return the path from the root to a given target label.

This is LeetCode 1104: Path In Zigzag Labelled Binary Tree.

For example, in a tree with 4 levels, label = 14 produces the path [1, 3, 4, 14]. The zigzag numbering means that level 0 reads [1], level 1 reads [3, 2] (right to left), level 2 reads [4, 5, 6, 7] (left to right), and level 3 reads [15, 14, 13, 12, 11, 10, 9, 8] (right to left).

Why this problem matters

This problem tests whether you can convert between two different numbering systems in a binary tree. In a standard complete binary tree, the parent of node n is n // 2. That formula breaks when the rows zigzag, because a label no longer maps directly to a position. You need to "undo" the reversal before applying the parent formula, then re-apply the reversal for the parent's level.

The key skill here is recognizing that the zigzag labelling is just a mirror operation on each reversed row. Once you see that, the whole algorithm collapses into a short loop with one formula per iteration.

Brute force

The brute force approach would be to construct the entire zigzag-labelled tree, then walk from the target node up to the root, collecting labels. You could build the tree level by level, alternating the label direction, and store parent pointers. For a tree with n levels, this uses O(2^n) time and space to build the tree before you even start finding the path.

def pathInZigZagTree(label):
    from collections import deque
    max_level = label.bit_length()
    parent = {}
    parent[1] = None
    for level in range(1, max_level):
        start = 1 << level
        end = (1 << (level + 1)) - 1
        if level % 2 == 1:
            labels = list(range(end, start - 1, -1))
        else:
            labels = list(range(start, end + 1))
        prev_start = 1 << (level - 1)
        prev_end = (1 << level) - 1
        if (level - 1) % 2 == 1:
            prev_labels = list(range(prev_end, prev_start - 1, -1))
        else:
            prev_labels = list(range(prev_start, prev_end + 1))
        for i, lbl in enumerate(labels):
            parent[lbl] = prev_labels[i // 2]
    path = []
    while label is not None:
        path.append(label)
        label = parent.get(label)
    return path[::-1]

This works but wastes enormous memory building a tree we never really need. The path itself has at most O(log n) nodes. We should be able to compute each parent directly with math.

The key insight

In a normal (non-zigzag) complete binary tree, node n sits at level floor(log2(n)), and its parent is n // 2. The zigzag labelling reverses alternate rows. For a reversed row, label L at level k occupies the same structural position as label (level_start + level_end - L) in a normal tree, where level_start = 2^k and level_end = 2^(k+1) - 1.

So to find the parent of a zigzag label:

1. Mirror the label within its level: mirrored = level_start + level_end - label
2. Compute the normal parent: mirrored // 2

The beautiful part is that this formula works regardless of whether the current level is reversed or not. The mirror-then-divide operation naturally produces the correct zigzag label at the parent level. You do not need to check whether a level is even or odd. The formula accounts for the alternation automatically because mirroring an already-mirrored label gives you the normal position, and mirroring a normal label gives you the reversed position.

Walking through it

Let's trace the algorithm for label = 14. At each step, we compute the parent using the mirror formula and collect the label into our path.

The algorithm builds the path from target to root in O(log n) steps, one per level. Each step uses only bit-length arithmetic and integer division. No tree construction needed.

Solution

def pathInZigZagTree(label):
    path = []
    while label >= 1:
        path.append(label)
        level = label.bit_length() - 1
        level_start = 1 << level
        level_end = (1 << (level + 1)) - 1
        label = (level_start + level_end - label) // 2
    return path[::-1]

Here is what each part does:

• path = [] collects labels from the target up to the root.
• label.bit_length() - 1 computes the level of the current label. In a complete binary tree, all labels at level k fall in the range [2^k, 2^(k+1) - 1), so the bit length tells you exactly which level you are on.
• level_start and level_end define the label range for the current level. level_start = 2^k and level_end = 2^(k+1) - 1.
• (level_start + level_end - label) // 2 is the mirror-and-divide formula. It first mirrors the label within its level (level_start + level_end - label), which converts a zigzag label to its structural equivalent, then divides by 2 to move up one level. The result is automatically the correct zigzag label at the parent level.
• path[::-1] reverses the collected path so it reads from root to target.

Complexity analysis

The optimal solution is O(log n) for both time and space, where n is the target label. The number of levels in the tree is floor(log2(n)) + 1, and we do constant work at each level.

Building blocks

This problem is built on two reusable patterns:

1. Bit-length level detection. In a complete binary tree, the level of label n is n.bit_length() - 1. This avoids computing floor(log2(n)) with floating point, which can have precision issues for large values:

level = label.bit_length() - 1
level_start = 1 << level
level_end = (1 << (level + 1)) - 1

2. Label mirroring within a range. To reflect a value x within the range [lo, hi], compute lo + hi - x. This maps the first element to the last, the second to the second-to-last, and so on. It is a general technique that appears whenever you need to reverse indexing within a bounded range:

mirrored = level_start + level_end - label

Edge cases

• label = 1 (root): The path is just [1]. The while loop appends 1, then computes (1 + 1 - 1) // 2 = 0, which exits the loop.
• label = 2 or label = 3 (level 1): The path has two elements. For label = 2, the parent is (2 + 3 - 2) // 2 = 1. For label = 3, the parent is (2 + 3 - 3) // 2 = 1.
• Large labels (up to 10^6): The bit-length approach handles large values without overflow or floating-point issues. Level 19 covers labels up to 1,048,575.
• Labels at level boundaries: Labels like 4 (start of level 2) and 7 (end of level 2) produce correct paths. The mirror formula handles both endpoints cleanly.

From understanding to recall

You just traced through a formula that mirrors a zigzag label and divides to find the parent. The math is compact: one bit-length call, two shifts, one subtraction, one division. It fits in five lines. It makes sense right now. But will you remember it under pressure?

The tricky part is not the code itself but remembering why the mirror formula works for both even and odd levels without a conditional. Spaced repetition locks in that insight. You practice writing the loop from memory at increasing intervals. First after a day, then three days, then a week. Each repetition reinforces the connection between bit-length, mirroring, and integer division until the pattern feels automatic.

The bit-length level detection and label mirroring patterns are two of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Drilling them individually with spaced repetition is far more effective than grinding random problems and hoping the patterns stick.

Related posts

• Binary Tree Right Side View - Another problem that requires reasoning about tree levels and positions within each level
• Binary Tree Level Order Traversal - The foundational level-by-level traversal pattern that helps you think about trees in terms of rows
• Construct Binary Tree from Preorder and Inorder Traversal - A tree reconstruction problem that also requires mapping between different indexing schemes

CodeBricks helps you internalize these tree math patterns so they become automatic. Instead of re-deriving the mirror formula from scratch every time, you build muscle memory through targeted repetition. The bit-length level detection and the label mirroring pattern each get their own drill, so you can practice them independently and combine them when this problem comes up.