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.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.