Can someone explain the same output in this question?
Like could you write the order of steps in for the first test case, which shows 14 as the answer?
Explain the sample output
Hi Aayush
In this question, a binary tree will be given int he form of h and n where h denotes hieght of the tree and n is the exit node if numbered left to right where the left most leaf node is 1 and the right most leaf node is 2^h. Now the string is LRLR… that is , alternate left and rights. It is asking how many nodes will be traversed by you before reaching the exit node if following the pattern as given in the question.
To dry run the first test case, the input is 3 and 8. The leaf nodes are from 1 to 2^3 which is 8. Hence the rightmost leaf node is the exit.
Now in this image the all the nodes are numbered , hence the 8th leaf node is the same as the 15th node of this tree. So our goal is to reach 15.
We start from root(1) so 1 (counter = 1) node traversed.
Next on L we go to left node of root which is 2 (counter = 2) .
next on R we go to 5(c = 3).
Next on L 10 (c= 4).
Now since 10 is a leaf node and not the exit, we move to the parent of 10 which is 5.
next on R 11(c = 5).
Again move to 5. Now since both 10 and 11 are traversed go to parent of 5 which is 2. We will then go to 4,9,8 making counter increase to 8.
Now we are back at 2. Since both 4 and 5 are traversed go to root node(1).
Now on R go to 3(c = 9).
Now on L 6(c= 10) again both 13,12 will be traversed making counter to 12.
Now on R 7(c = 13).
Then L 14(c = 14). then go to 7 as non exit leaf node. Finally reach 15 (exit node)
Hence answer is 14 (nodes traversed BEFORE reaching exit node)
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.