Leetcode 1104. Path In Zigzag Labelled Binary Tree

Problem

We have a binary tree which is labelled in row order, where the odds numbered rows are labelled left to right, and the even numbered rows are labelled right to left. Given the label of a node in this tree, our task is to return the labels in the path from the root of the tree to the node with that label.

In short, we would like to find the path from root to a node in an infinitely large binary tree, where the nodes are labelled in sequence, but the labelling direction switches between right to left and left to right each level.

Example Walkthrough

Consider the following example,

Input: label = 14

Output: [1,3,4,14]

Here, our task is to find the path from the root node to the node with label 14.

Starting from the root, the first step is to node 3 (the second left child), then to node 4 (the first right child of node 3) and finally to node 14. So, the returned path should be [1,3,4,14]

Approach

Finding the height, or level, of the node in tree, which is largest 'l' such that 2^l <= label, would be the first step.

The next step would be to check if the current level is odd. If it is, compute the label of the node in a tree where all levels are labelled left-to-right (which is sum of highest and lowest labels in the current level minus the label of the current node) and replace the current label with it.

Finally, starting from the level where the node lies, move upwards towards the root node and continue to update the label as discussed above. Add these labels to the list in reverse order.

This approach will give us the path from root node to the given node.

Python Solution

1
2python
3class Solution:
4    def pathInZigZagTree(self, label: int) -> List[int]:
5        res = []
6        while label != 0:
7            res.append(label)
8            label >>= 1
9        res = res[::-1]
10        if len(res) % 2 == 0:
11            for i in range(2, len(res), 2):
12                t = 2 ** i
13                res[i] = t - 1 - res[i] + t // 2
14        else:
15            for i in range(1, len(res), 2):
16                t = 2 ** i
17                res[i] = t - 1 - res[i] + t // 2
18        return res

Java Solution

1
2java
3class Solution {
4    public List<Integer> pathInZigZagTree(int label) {
5        LinkedList<Integer> result = new LinkedList<>();
6        int parent = label;
7        result.addFirst(parent);
8
9        while(parent != 1) {
10            int d = (int)(Math.log(parent) / Math.log(2));
11            int offset = (int)Math.pow(2, d+1) - 1 - parent;
12            parent = ((int)Math.pow(2, d) + offset) / 2;
13            result.addFirst(parent);
14        }
15        return result;
16    }
17}

Javascript Solution

1
2javascript
3var pathInZigZagTree = function(label) {
4    let result = [];
5    while(label != 0) {
6        result.unshift(label);
7        label = Math.floor(label/2);
8    }
9    for(let i = result.length-2; i > 0; i-=2) {
10        result[i] = (2**i + 2**(i+1) - 1 - result[i]);
11    }
12    return result;
13};

C++ Solution

1
2cpp
3class Solution {
4public:
5    vector<int> pathInZigZagTree(int label) {
6        vector<int> res;
7        while(label != 0) {
8            res.push_back(label);
9            label >>= 1;
10        }
11        reverse(res.begin(), res.end());
12        if(res.size()%2 == 0) {
13            for(int i = 2; i < res.size(); i+=2) {
14                int t = 1 << (i+1);
15                res[i] = ((t/2)+(t/2-1))-res[i];
16            }
17        }
18        else {
19            for(int i = 1; i < res.size(); i+=2) {
20                int t = 1 << (i+1);
21                res[i] = ((t/2)+(t/2-1))-res[i];
22            }
23        }
24        return res;
25    }
26};

C# Solution

1
2csharp
3public class Solution {
4    public IList<int> PathInZigZagTree(int label) {
5        List<int> res = new List<int>();
6        while(label != 0){
7            res.Add(label);
8            label /= 2;
9        }
10        res.Reverse();
11        for(int i = 0; ((i < res.Count) && ((res.Count - i) % 2 == 0)); i += 2){
12            int logVal = (int)Math.Log(res[i], 2);
13            int start = (int)Math.Pow(2, logVal);
14            int end = (int)Math.Pow(2, logVal + 1) - 1;
15            res[i] = start + end - res[i];
16        }
17        
18        return res;
19    }
20}

Scala Solution

1
2scala
3object Solution {
4    def pathInZigZagTree(label: Int): List[Int] = {
5        var res: List[Int] = List(label)
6        var currentLabel = label
7        while (currentLabel > 1) {
8            val level = 31 - Integer.numberOfLeadingZeros(currentLabel)
9            val prevLevel = level - 1
10            val isFirstHalf = (currentLabel - (1 << level)) / (1 << prevLevel) < 2
11            val parent = if (isFirstHalf) ((3 * (1 << prevLevel)) - 1 - ((currentLabel - (1 << level)) / 2)) else (currentLabel / 2)
12            res = parent +: res
13            currentLabel = parent
14        }
15        res
16    }
17}

Ruby Solution

1
2ruby
3def path_in_zig_zag_tree(label)
4    res = []
5    while label > 0
6      res.unshift(label)
7      label >>= 1
8    end
9    level = res.size
10    if level.even?
11      (1...level).step(2) do |i|
12        l = 1 << i
13        h = (1 << (i + 1)) - 1
14        res[i] = l + h - res[i]
15      end
16    else
17      (0...level).step(2) do |i|
18        l = 1 << i
19        h = (1 << (i + 1)) - 1
20        res[i] = l + h - res[i]
21      end
22    end
23    res
24end

To sum up, In this problem, visualizing the process of traversing the binary tree in a zigzag manner and understanding the changes that occur when moving across different levels in the tree is key. The solutions in the above mentioned programming languages follow these steps – identifying the level of the node, calculating parent nodes and creating the path from root to the node by following the parents.