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}

• Initialize a result list, preferably a LinkedList for efficient prepending.
• Start with the target label and loop until you reach the root.
• In each step of the loop, add the current label to the front of the result list.
• Calculate the parent of the current label. This is the key step.
  • First, determine the level of the current label (level = floor(log2(label))).
  • Find the minimum (min = 2^level) and maximum (max = 2^(level+1) - 1) possible labels at this level.
  • The parent's label can be found with a single, clever observation: the parent of a node l is located at the same position as the parent of its symmetrical counterpart in the level. The symmetrical label is min + max - l. In a standard binary tree, the parent of a node x is x/2. Therefore, the parent of our node l is (min + max - l) / 2.
• Update label to its calculated parent's label.
• Continue the loop until label becomes 1 (the root), which is also added to the path.
• Return the constructed path.

This method leverages the mathematical structure of the tree. The path is constructed by starting at the given label and iteratively moving to its parent until the root (label 1) is reached.

The core of the algorithm is the formula to find a parent's label. For any node with label at a certain level, we can find its parent by:

1. Determining the level of the current label. This can be calculated as floor(log2(label)).
2. Finding the range of labels for that level. The first label is 2^level and the last is 2^(level+1) - 1.
3. A key insight is that the parent of a node l and the parent of its symmetrical node l' are the same. The symmetrical node l' is the one that is at the same position from the other end of the row. Its value is (min_label + max_label) - l.
4. In a standard binary tree, the parent of any node x is x/2. This property holds for the positional structure of our tree. By finding the sum of a node's label and its symmetrical counterpart's label, we effectively cancel out the zigzag effect for that level. Dividing this sum by 2 gives us the parent's label in the level above.
5. So, the parent of label can be calculated as parent = (min_label_at_level + max_label_at_level - label) / 2.

We repeat this calculation, adding each label to the front of our path list, until we reach the root.

1import java.util.*;2 3class Solution {4    public List<Integer> pathInZigZagTree(int label) {5        LinkedList<Integer> path = new LinkedList<>();6        int currentLabel = label;7 8        // Determine the initial level of the label9        int level = 0;10        if (label > 1) {11            level = (int) (Math.log(label) / Math.log(2));12        }13 14        while (currentLabel >= 1) {15            path.addFirst(currentLabel);16            if (currentLabel == 1) {17                break;18            }19 20            // Calculate the range of labels for the current level21            int minAtLevel = 1 << level;22            int maxAtLevel = (1 << (level + 1)) - 1;23 24            // Calculate the parent's label25            currentLabel = (minAtLevel + maxAtLevel - currentLabel) / 2;26            level--;27        }28 29        return path;30    }31}