Path In Zigzag Labelled Binary Tree

Moderate
0/80
Average time to solve is 10m
2 upvotes
Asked in company
Microsoft

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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.
Sample Input 1:
2
26
44
Sample output 1:
1 2 6 10 26
1 2 6 11 25 44
Explanation:
Test Case 1:

The output [1, 2, 6, 10, 26] is the required shortest list of labels which Ninja can travel to reach and defeat the enemy.


Test Case 2:

The output [1, 2, 6, 11, 25, 44] is the required shortest list of labels which Ninja can travel to reach and defeat the enemy.
Sample Input 2:
2
14
50
Sample output 2:
1 3 4 14
1 3 5 12 22 50
Hint

Try to first build a tree that contains nodes for all the values up until the “label” which is given as input.

Approaches (2)
Path In Zigzag Labelled Binary Tree

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.
Time Complexity

O(N + log(N)) ~ O(N), where ‘N’ is the value of the given ‘LABEL’.

 

Since we are building a tree with indexes level for the zig-zag tree by iterating over all the nodes which takes O(N) time. After that for every node, we are also finding the parent node until we reach the root node (which is 1) which is reducing the traversal of the tree in the order of the depth i.e. log(N). Hence the complexity here grows by O(N + log(N)) ~ O(N).

Space Complexity

O(N + log(N)) ~ O(N), where ‘N’ is the value of the given ‘LABEL’

 

Since, here, we require a log(N) amount of space, i.e equal to the depth of the tree which we are traversing. But we are also building up level-wise indexes of the nodes in the binary tree which requires O(N) space, therefore, the space complexity is O(N + log(N)) ~ O(N).

Code Solution
(100% EXP penalty)
Path In Zigzag Labelled Binary Tree
Full screen
Console