Problem Description

Given a binary tree with zigzag level order labeling, where the labels of the nodes follow a pattern: the root node is labeled 1, the next level is labeled from left to right as 2, 3, the next from right to left as 4, 5, 6, 7, and so on, alternating direction at each level.

You are given an integer label representing the value of a node in this tree. Your task is to return the path in the tree from the root to the node with that label, as a list of the labels along the path.

Constraints:

• 1 <= label <= 10⁶
• There is always exactly one valid path from the root to the node with the given label.

Thought Process

At first glance, the problem seems similar to finding the path from the root to a node in a perfect binary tree. In a regular binary tree labeled in level order, the parent of any node with label n is simply n // 2. However, the twist here is the zigzag labeling, which reverses the order of labels at every other level.

This means that, to move up the tree, we need to "undo" the zigzag at each level to map the current label to its "true" position in a normal binary tree, find its parent, and then map that back into the zigzag labeling for the parent level.

The brute-force approach would be to build the actual tree or simulate the labelings, but that's inefficient for large labels. Instead, we need to find a mathematical way to determine the path efficiently, working backwards from the given label up to the root, reconstructing the path as we go.

Solution Approach

Let's break down the solution into clear steps:

1. Determine the Level of the Label:
   The number of nodes doubles at each level. For example, level 0 (root) has 1 node, level 1 has 2 nodes, level 2 has 4 nodes, etc. The range of labels at level l is [2^l, 2^{l+1} - 1]. We can find the level by repeatedly dividing label by 2 until we reach 0.
2. Iteratively Find the Parent at Each Level:
   For each level, we need to know:
   • What is the "normal" label (as if the tree was not zigzagged)?
   • What is the actual zigzag label at that level?
   At every odd level (starting from 1), the labeling is reversed. To get the "normal" label, we use:
   normal_label = min_label + max_label - label
   where min_label = 2^level and max_label = 2^{level+1} - 1.
3. Move Up the Tree:
   The parent in a regular binary tree is normal_label // 2. After finding the parent, if the parent level is zigzagged, we need to convert the normal parent label back to its zigzag label using the same formula.
4. Repeat Until the Root:
   Continue this process, adding each label to the path, until we reach the root node labeled 1.
5. Reverse the Path:
   Since we built the path from the target label up to the root, we reverse it before returning.

Example Walkthrough

Let's take label = 14 as an example.

Step 1: Find Level
- Level 0: [1]
- Level 1: [2, 3]
- Level 2: [4, 5, 6, 7]
- Level 3: [8, 9, 10, 11, 12, 13, 14, 15] (zigzag, so order is reversed)

14 is at level 3.

Step 2: Build Path from 14 up to 1

• Level 3: Label is 14. Since this level is zigzagged, its "normal" label is:
  min_label = 8, max_label = 15
normal_label = 8 + 15 - 14 = 9
• Parent (Level 2): Parent in normal tree: 9 // 2 = 4.
  Level 2 is not zigzagged, so zigzag label is also 4.
• Level 2: Add 4 to path.
• Parent (Level 1): 4 // 2 = 2. Level 1 is zigzagged.
  min_label = 2, max_label = 3
zigzag_label = 2 + 3 - 2 = 3
• Level 1: Add 3 to path.
• Parent (Level 0): 2 // 2 = 1. Level 0 is not zigzagged, so label is 1.
• Level 0: Add 1 to path.

Time and Space Complexity

Brute-force Approach:
If we built the entire tree or its levels, the time and space complexity would be O(N), where N is the number of nodes up to label. For label up to 10⁶, this is inefficient.

Optimized Approach:
Our solution computes the path by moving up the tree one level at a time. The height of the tree is O(log label), since each level halves the range. Thus:

• Time Complexity: O(log label)
• Space Complexity: O(log label) (for the path list)

Summary

The key insight is to mathematically map between zigzag and normal level order labeling, using the formula min_label + max_label - label at zigzagged levels. By tracing the path from the given label up to the root, converting between zigzag and normal labels as needed, we efficiently construct the path without building the tree. This solution is both elegant and optimal, running in logarithmic time and space.

Code Implementation

class Solution:
    def pathInZigZagTree(self, label: int) -> list[int]:
        path = []
        level = 0
        n = label
        # Find the level of the label
        while (1 << level) <= label:
            level += 1
        level -= 1

        while label >= 1:
            path.append(label)
            # Compute the min and max label at this level
            level_min = 1 << level
            level_max = (1 << (level + 1)) - 1
            # For zigzag levels (odd indexed), map to normal label
            label = (level_min + level_max - label) // 2
            level -= 1

        return path[::-1]
      

class Solution {
public:
    vector<int> pathInZigZagTree(int label) {
        vector<int> path;
        int level = 0, n = label;
        while ((1 << level) <= label) ++level;
        --level;
        while (label >= 1) {
            path.push_back(label);
            int level_min = 1 << level;
            int level_max = (1 << (level + 1)) - 1;
            label = (level_min + level_max - label) / 2;
            --level;
        }
        reverse(path.begin(), path.end());
        return path;
    }
};
      

class Solution {
    public List<Integer> pathInZigZagTree(int label) {
        List<Integer> path = new ArrayList<>();
        int level = 0, n = label;
        while ((1 << level) <= label) level++;
        level--;
        while (label >= 1) {
            path.add(label);
            int level_min = 1 << level;
            int level_max = (1 << (level + 1)) - 1;
            label = (level_min + level_max - label) / 2;
            level--;
        }
        Collections.reverse(path);
        return path;
    }
}
      

var pathInZigZagTree = function(label) {
    let path = [];
    let level = 0;
    while ((1 << level) <= label) level++;
    level--;
    while (label >= 1) {
        path.push(label);
        let level_min = 1 << level;
        let level_max = (1 << (level + 1)) - 1;
        label = Math.floor((level_min + level_max - label) / 2);
        level--;
    }
    return path.reverse();
};