Find path through binary tree to get to desired node #

binarybinary operations

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.

Best Answer

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.

Related Question