Traversing through a binary tree

Question

Consider a full binary tree of n nodes numbered from 1 to n in the common top-down left-to-right manner. For the sake of the question, we can consider the following tree:

     1
   /   \
  2     3
 / \   / \
4   5 6   7

I need to traverse from the root to some other node. Let's say I need to traverse to 6.

Because I can see it from the picture, I know I have to go right to 3 and then left to 6. But I need to be able to find that out mathematically without a picture.

When I am in the root, how do I know that 6 is in the right sub-tree and not in the left one? And then when I am in 3, how do I know that 6 is in the left sub-tree and not in the left one?

Answer 1

A possible solution: Let $a$ be the number where you currently are and $b$ the number you want to reach. If $a$ has $n$ bits (in binary), then look at the $(n+1)^{th}$ bit of $b$, starting from left (upper bits). If it is $0$, go left, if it is $1$ go right.

Example $a = 3$ and $b = 6$. $a$ has $2$ bits in binary. Then the $3^{rd}$ bit of $b$ is $0$ starting from the upper bits: go left.

Answer 2

You need a sorted binary tree, so, with those numbers, approximate and pick the mean number, say 3. This will result in a more balanced tree:

    3
   / \

Recursively do the same for those numbers $\leq 3$ on the left branch and those $\gt 3$ on the right branch. So:

     3
    / \
   2   6
  /   / \
 1   4   7
      \
       5

Now when you insert() into the data structure, you add one number at a time and you can find its place by comparing to each node value and moving left or right depending on the result ($\leq, \lt$). If you add in something already in the tree, just keep the value already in the tree. That's the basic algorithm any way.

Answer 3

$6=110_2$. Go right, left. (After the initial $1$ (at the root), for subsequent bits, go left for a $0$, right for a $1$.)