# Path In Zigzag Labelled Binary Tree
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/path-in-zigzag-labelled-binary-tree)
Canonical: https://scaleengineer.com/dsa/problems/path-in-zigzag-labelled-binary-tree
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math)
**Data structures:** Tree, Binary Tree
---
## Problem
In an infinite binary tree where every node has two children, the nodes are labelled in row order.

In the odd numbered rows (ie., the first, third, fifth,...), the labelling is left to right, while in the even numbered rows (second, fourth, sixth,...), the labelling is right to left.

![](https://assets.glich.co/dsa/path-in-zigzag-labelled-binary-tree/image0.png)

Given the `label` of a node in this tree, return the labels in the path from the root of the tree to the node with that `label`.

**Example 1:**

**Input:** label = 14
**Output:** [1,3,4,14]

**Example 2:**

**Input:** label = 26
**Output:** [1,2,6,10,26]

**Constraints:**

* `1 <= label <= 10^6`

# Approaches
## Brute-Force Tree Construction
This approach involves a direct simulation of the tree's construction. We build the tree level by level up to the level containing the target `label`. While building, we maintain a map of each node's label to its parent's label. After the necessary portion of the tree is constructed and the parent relationships are mapped, we can easily backtrack from the target `label` to the root to find the required path.
**Time:** O(label) - To find the path for a given `label`, we must construct the tree up to the level of that label. The number of nodes in the tree grows exponentially with the level. The total number of nodes processed is proportional to the value of `label` itself. · **Space:** O(label) - The space required is dominated by the `parentMap` and the queue used for level-order traversal. In the worst case, we might store information for all nodes up to the level of the target `label`. The number of nodes up to level `d` is `2^(d+1) - 1`. Since `d` is `log2(label)`, the number of nodes is approximately `2*label`.
**Pros:** Straightforward to implement as it directly follows the problem's description.; Easy to reason about and debug.
**Cons:** Highly inefficient for large labels as both time and space complexity are linear with respect to the label value.; Can lead to `OutOfMemoryError` for labels close to the constraint `10^6`.
### Explanation
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.

```java
import java.util.*;

class Solution {
    public List<Integer> pathInZigZagTree(int label) {
        if (label == 1) {
            return Collections.singletonList(1);
        }

        Map<Integer, Integer> parentMap = new HashMap<>();
        parentMap.put(1, 0); // Using 0 as a sentinel for no parent

        Queue<Integer> queue = new LinkedList<>();
        queue.add(1);
        int level = 0;
        boolean found = false;

        while (!queue.isEmpty() && !found) {
            int levelSize = queue.size();
            level++;
            int start = 1 << level;
            int end = (1 << (level + 1)) - 1;
            List<Integer> children = new ArrayList<>();
            if (level % 2 == 1) { // Even row number, R-L labeling
                for (int i = end; i >= start; i--) {
                    children.add(i);
                }
            } else { // Odd row number, L-R labeling
                for (int i = start; i <= end; i++) {
                    children.add(i);
                }
            }

            for (int i = 0; i < levelSize; i++) {
                int parent = queue.poll();
                int child1 = children.get(2 * i);
                int child2 = children.get(2 * i + 1);
                parentMap.put(child1, parent);
                parentMap.put(child2, parent);
                queue.add(child1);
                queue.add(child2);
                if (child1 == label || child2 == label) {
                    found = true;
                }
            }
        }

        LinkedList<Integer> path = new LinkedList<>();
        int current = label;
        while (current != 0) {
            path.addFirst(current);
            current = parentMap.get(current);
        }
        return path;
    }
}
```
### Algorithm
*   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.

## Mathematical Parent Calculation
A much more efficient approach is to work backward from the target node to the root. Instead of building the tree, we can mathematically compute the label of a node's parent at each step. This avoids the high time and space costs of simulation. The key is to understand the relationship between a node's label, its level in the tree, and the labeling direction (left-to-right vs. right-to-left).
**Time:** O(log label) - The algorithm iterates from the node's level up to the root. The number of levels (the height of the tree) is proportional to `log(label)`. Each iteration involves a few constant-time arithmetic calculations. · **Space:** O(log label) - The space is used to store the resulting path. The length of the path is equal to the depth of the node, which is `log2(label) + 1`.
**Pros:** Extremely efficient with logarithmic time and space complexity.; Scales perfectly for large inputs up to the given constraints.; Requires no large data structures, avoiding memory issues.
**Cons:** The mathematical logic can be non-obvious and requires careful derivation to ensure correctness.; Relies on properties of complete binary trees and bitwise operations, which might be less familiar.
### Explanation
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.

```java
import java.util.*;

class Solution {
    public List<Integer> pathInZigZagTree(int label) {
        LinkedList<Integer> path = new LinkedList<>();
        int currentLabel = label;

        // Determine the initial level of the label
        int level = 0;
        if (label > 1) {
            level = (int) (Math.log(label) / Math.log(2));
        }

        while (currentLabel >= 1) {
            path.addFirst(currentLabel);
            if (currentLabel == 1) {
                break;
            }

            // Calculate the range of labels for the current level
            int minAtLevel = 1 << level;
            int maxAtLevel = (1 << (level + 1)) - 1;

            // Calculate the parent's label
            currentLabel = (minAtLevel + maxAtLevel - currentLabel) / 2;
            level--;
        }

        return path;
    }
}
```
### Algorithm
*   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.

# Solutions
### Java

```java
class Solution {
public
  List<Integer> pathInZigZagTree(int label) {
    int x = 1, i = 1;
    while ((x << 1) <= label) {
      x <<= 1;
      ++i;
    }
    List<Integer> ans = new ArrayList<>();
    for (; i > 0; --i) {
      ans.add(label);
      label = ((1 << (i - 1)) + (1 << i) - 1 - label) >> 1;
    }
    Collections.reverse(ans);
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<int> pathInZigZagTree(int label) {
    int x = 1, i = 1;
    while ((x << 1) <= label) {
      x <<= 1;
      ++i;
    }
    vector<int> ans;
    for (; i > 0; --i) {
      ans.push_back(label);
      label = ((1 << (i - 1)) + (1 << i) - 1 - label) >> 1;
    }
    reverse(ans.begin(), ans.end());
    return ans;
  }
};

```

### Python

```python
class Solution:
    def pathInZigZagTree(self, label: int) -> List[int]: x = i = 1 while (x << 1) <= label: x <<= 1 i += 1 ans = [0] * i while i: ans[i - 1] = label label = ((1 << (i - 1)) + (1 << i) - 1 - label) >> 1 i -= 1 return ans

```