Path In Zigzag Labelled Binary Tree

medium math binary tree zigzag

Problem

In an infinite binary tree the rows are labelled 1, 2, 3, … from the top. In odd-numbered rows the labels increase left to right, while in even-numbered rows they increase right to left (a zigzag). Given the label of a node, return the labels on the path from the root of the tree to that node.

Inputlabel = 14

Output[1, 3, 4, 14]

Row 4 is reversed, so node 14 sits where a normal tree would have 9; its parent chain mirrors back up to the root.

label

def path_in_zigzag_tree(label):
    path = []
    level = label.bit_length() - 1
    while label >= 1:
        path.append(label)
        # mirror within the level, then move to the parent
        lo, hi = 1 << level, (1 << (level + 1)) - 1
        label = (lo + hi - label) // 2
        level -= 1
    return path[::-1]

function pathInZigZagTree(label) {
  const path = [];
  let level = 31 - Math.clz32(label);
  while (label >= 1) {
    path.push(label);
    const lo = 1 << level;
    const hi = (1 << (level + 1)) - 1;
    label = Math.floor((lo + hi - label) / 2);
    level -= 1;
  }
  return path.reverse();
}

class Solution {
    public List<Integer> pathInZigZagTree(int label) {
        List<Integer> path = new ArrayList<>();
        int level = 31 - Integer.numberOfLeadingZeros(label);
        while (label >= 1) {
            path.add(label);
            int lo = 1 << level;
            int hi = (1 << (level + 1)) - 1;
            label = (lo + hi - label) / 2;
            level--;
        }
        Collections.reverse(path);
        return path;
    }
}

vector<int> pathInZigZagTree(int label) {
    vector<int> path;
    int level = 31 - __builtin_clz(label);
    while (label >= 1) {
        path.push_back(label);
        int lo = 1 << level;
        int hi = (1 << (level + 1)) - 1;
        label = (lo + hi - label) / 2;
        level--;
    }
    reverse(path.begin(), path.end());
    return path;
}

Explanation

In a normal complete binary tree the parent of a node is simply node // 2. The only complication here is the zigzag: even rows have their labels reversed. The fix is to un-reverse a label before halving.

We climb from the given node up to the root. At each step we know the node's level, whose labels span the range [lo, hi] where lo = 2^level and hi = 2^(level+1) - 1. To undo the reversal, we mirror the label within that range: the mirror of label is lo + hi - label. After mirroring, the ordinary parent formula mirror // 2 gives the parent's label, and we move up one level.

We append each label as we climb, which collects the path bottom-up. At the end we reverse the list so it reads from the root down to the node.

Example: label = 14 on level 3 (range [8, 15]). Mirror it: 8 + 15 - 14 = 9, parent 9 // 2 = 4. Continue up from 4 and 3 until you reach 1. Reversed, the path is [1, 3, 4, 14].

Each step climbs one level, so the work grows with the number of levels, which is logarithmic in the label.

Time: O(log label) Space: O(log label)