Last Updated: 15 Apr, 2021
Path In Zigzag Labelled Binary Tree
Moderate
Asked in company
Ninja is chasing an enemy hiding in a labeled node 'LABEL' in an infinite binary tree where every node has two children. The nodes are labeled in row order but the enemy has shifted the order of the nodes of the tree to hide from the Ninja in such a way that now in the odd-numbered level (ie., the first, third, fifth,...), the labeling is left to right, while in the even-numbered level (second, fourth, sixth,...), the labeling is right to left.
Now given the ‘LABEL’ of the node in the tree where the enemy is hiding, return the labels of the nodes in the shortest path from the root of the tree to the node 'LABEL' which Ninja should follow to reach and defeat the enemy quickly.
Example:
Suppose given ‘LABEL’ is ‘14’ then:
The shortest path in the zigzag binary tree from the root where the Ninja starts to reach the node with the given label where the enemy is hiding is 1 -> 3 -> 4 -> 14.
Input Format
The first line of input contains a single integer ‘T’ denoting the number of test cases given. Then next ‘T’ lines follow:
The first line of each test case input contains a single integer i.e. the ‘LABEL’ of the node where the enemy is hiding.
Output Format:
For every test case, print a single line containing space-separated integers denoting the labels of the nodes in the shortest path from the root of the tree to the node 'LABEL' which Ninja can follow to reach and defeat the enemy quickly.
Print the list/vector of the elements from the root to the node 'LABEL'.
The output of each test case will be printed in a separate line.
Note:
You do not need to print anything; it has already been taken care of. Just implement the given function.
Constraints :
1 <= ‘T’ <= 10 ^ 4
1 <= ‘LABEL’ <= 10 ^ 6
Time Limit: 1 sec.
Where 'T' denotes the number of test cases and 'LABEL' denotes the label of the node the enemy is hiding in.
Time limit: 1 sec.
Approaches
The basic idea behind the algorithm is fairly to realize that if you take the node that corresponds to the label given as input then you can assign an index value to that node. Then take that index value and divide it by two. This will give the index value of the parent node and keep repeating the above idea to get all the nodes from root to label.
The algorithm to calculate the required will be:-
- Initialise a ‘RESULT’ list/vector which would contain the final path nodes.
- Now, start by building up the required tree that contains the nodes for all the values up until the ‘LABEL’ that is given as input. For that, use nested lists/vector to represent each level of the tree. The levels in the list/vector are filled following a zigzag pattern, this can be done as :
- Keep a mark to check which level is being filled for the tree in each iteration. Based on whether the level is odd or even start filling up the values of the indexes which would be there for the tree nodes.
- If the level is odd, fill the values from left to right while the order can be reversed if the level is even.
- Return the completed indexes of the levels in the zig-zag tree.
- Now get the index of our label node ‘LABEL’ using the tree of indexes that we built previously.
- For each label recursively take that index value, add it to our result and divide by two to get the index value of the parent node until we reach the root node (1 or index 0).
- After this the resultant list/vector can now be returned.
The basic idea behind the algorithm is fairly straightforward that first, we can add the node (‘LABEL’ given) to the back of the result list. Find the depth of the node. Find the parent of the node. Repeat steps with the parent as the new node.
The algorithm to calculate the required will be:-
- Start by calculating the current depth of the given ‘LABEL’ in the tree which can be calculated using the fact that the depth of the tree for a given value of a node can be found by taking its logarithm with base 2.
- Now, calculate the offset value for each depth ‘d’, where the values of the nodes lie from 2 ^ d -> 2 ^ (d + 1) - 1.
- Find the real parent based on offset calculated before as:
- parent = (2 ^ depth + offset) / 2;
- Keep adding the calculated parent in the list (array) of our obtained nodes.
- Repeat the above steps until we reach 1 (root node) and return the list (array).