Find path through binary tree to get to desired node #

Question

Say we have a binary tree. If know how many nodes X there are in the tree, how can we navigate from the root node to the node with value X without any backtracking? I am doing binary arithmetic and seeing some patterns but can't make the breakthrough.

Here is a sample tree:

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

It seems to be better to start with 1 instead of 0 for root node, but not sure if it matters much really. My guess to start at the root node and take the left path Y times, and then if necessary go to right node from there, and then you have a new tree, with the same problem but smaller tree.

So if X = 16, we take the left path 4 times, followed by 0 right path. but if X = 11, we take a left path 1 times, and right path twice.

I know there is a pattern here but can't figure it out lol.

Actual goal: My actual goal is to find the next node on the tree to add a child to, given the number of current nodes on the tree. This is part of heap implementation. In the tree above, the node to add to is #8, for a balanced binary tree.

Answer 1

Write the number of the node in binary. Ignore the first bit, which is always $1$. Read the remainder from left to right: a $0$ means go left, and a $1$ means go right. For instance, $10$ is $1010_2$, so it is reached by branching $010=LRL$. Its left child is $LRLL$, corresponding to $0100$ and hence to the number $10100_2=20$; its right child is $LRLR$, corresponding to $0101$ and hence to the number $10101_2=21$.

To find the parent of node $n$, write $n$ in binary, remove the last bit, and write the result in decimal. Equivalently, the parent node’s number is $\left\lfloor\frac{n}2\right\rfloor$, since dropping the last bit is dividing by $2$ and ignoring any remainder.

Answer 2

At node labelled $v$, the left child is having label $2v$ and the right child is having label $2v+1$. So the parent node of a node labelled $x$ is labelled $\lfloor x/2\rfloor$.

This allows us to figure out the reverse path easily. From $16\to\lfloor16/2\rfloor=8\to\lfloor8/2\rfloor=4\to\lfloor4/2\rfloor=2\to\lfloor2/2\rfloor=1$. So the path you have to follow is: $1,2,4,8,16$.

Now it becomes easy to figure out whether you have to go left or right. If the next node in the path is having odd label, we are to take the right child. If it is having an even label, take the left child. You can do this process simultaneously with the process of finding the parent node.