Path In Zigzag Labelled Binary Tree

• Determine the level of the target label. Let this be max_level.
• Create a map to store parent-child relationships, for instance, Map<Integer, Integer> parentMap.
• Simulate the tree construction level by level from the root (level 0) up to max_level.
• For each level, calculate the range of labels and generate them according to the zigzag pattern (left-to-right for odd rows, right-to-left for even rows).
• As each level's nodes are generated, populate the parentMap by linking them to their parents from the previous level.
• Once the map is built, trace the path from the target label back to the root by repeatedly querying the parentMap.
• Collect the labels in a list and reverse it to obtain the final path from root to target.

The algorithm proceeds as follows:

1. First, we determine the depth of the tree required to include the given label. The level d of a node with a given label can be found by d = floor(log2(label)).
2. We then construct the tree level by level. We use a list to hold the labels of the nodes at the current level and a map to store child -> parent mappings.
3. We start with level 0, which contains only the root node with label 1.
4. We then iterate from level 1 up to the target level. In each iteration, we generate the labels for the new level. The labels are generated from left-to-right (2^d to 2^(d+1)-1) if the row number is odd (i.e., level d is even), and right-to-left if the row number is even (i.e., level d is odd).
5. For each parent in the previous level, we associate its two children from the newly generated list of labels and update our parent map.
6. After the simulation is complete, the parentMap contains all the necessary links to trace the path. We start from the target label, add it to our result path, and then find its parent from the map. We repeat this process until we reach the root (label 1).
7. Finally, the collected path is reversed to get the correct order from root to the target node.

1import java.util.*;2 3class Solution {4    public List<Integer> pathInZigZagTree(int label) {5        if (label == 1) {6            return Collections.singletonList(1);7        }8 9        Map<Integer, Integer> parentMap = new HashMap<>();10        parentMap.put(1, 0); // Using 0 as a sentinel for no parent11 12        Queue<Integer> queue = new LinkedList<>();13        queue.add(1);14        int level = 0;15        boolean found = false;16 17        while (!queue.isEmpty() && !found) {18            int levelSize = queue.size();19            level++;20            int start = 1 << level;21            int end = (1 << (level + 1)) - 1;22            List<Integer> children = new ArrayList<>();23            if (level % 2 == 1) { // Even row number, R-L labeling24                for (int i = end; i >= start; i--) {25                    children.add(i);26                }27            } else { // Odd row number, L-R labeling28                for (int i = start; i <= end; i++) {29                    children.add(i);30                }31            }32 33            for (int i = 0; i < levelSize; i++) {34                int parent = queue.poll();35                int child1 = children.get(2 * i);36                int child2 = children.get(2 * i + 1);37                parentMap.put(child1, parent);38                parentMap.put(child2, parent);39                queue.add(child1);40                queue.add(child2);41                if (child1 == label || child2 == label) {42                    found = true;43                }44            }45        }46 47        LinkedList<Integer> path = new LinkedList<>();48        int current = label;49        while (current != 0) {50            path.addFirst(current);51            current = parentMap.get(current);52        }53        return path;54    }55}