Find the node that we will reach with a given path on a graph (complete binary tree)

Question

This question is regarding a special case of graph i.e. complete binary tree

Consider the following tree :-

                          1
                    /           \
              2                   3
            /   \                /       \
         4       5               6        7
        / \      /  \          /  \       /  \
       8  9      10 11         12 13      14 15

And the Path is given as as combination of L and R

For eg :-

1. Path LLR will be like 1->2->4->9

2. Path RLR will be like 1->3->6->13

Assuming that such a tree is infinite, I need to calculate the node number on a level. I used the following approach :-

1. Path LLR Length of path is 3 so answer will be at level 4 (since we are starting at root @ level 0) LLR taken as L=0 and R=1 becomes 001 = 1 And if we assume that one level is a array starting with 0, which in this case is [8,9,10,11,12,13,14,15,16,17] then $1^{st}$ element is to be chosen which is 9 and our answer.

2. Path RLR Length of path is 3 so answer will be at level 4 (since we are starting at root @ level 0) RLR taken as L=0 and R=1 becomes 101 = 5 And if we assume that one level is a array starting with 0, which in this case is [8,9,10,11,12,13,14,15] then $5^{th}$ element is to be chosen which is 13 and our answer.

But the problem is that I can have this path length upto 10 power 5. Which makes it difficult for computers to calculate. So, is there a better way to find the needed node on this graph ?

Sorry, for making a mess, I have tried to be as clear as possible. Let me know if I need to change anything in this question. Thanks.

Answer 1

Use binary for the node numbers and for the directions. So if your string of directions (like LLR) is $X_1X_2X_3\dots$, then the node number is $1X_1X_2X_3\dots$ where you take $X_1=0$ for L and $X_1=1$ for R.