1

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?

zbr
  • 113

3 Answers3

2

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.

user3017842
  • 281
  • Thank you for the answer, it seems to work. However, I was hoping for a more straightforward solution in the decimal system. Do you think there is none? If none gets presented in some time, I will accept your answer as it seems the best to me so far. – zbr Mar 12 '15 at 11:54
  • You're welcome. I believe that any other solution will boil down to the same thing. To compute mathematically the number of bits of a number $a$, you can use the formula $n = \lfloor log_2(a) \rfloor+1$ and the $k^{th}$ bit of a number is given by $\lfloor\frac{a}{2^{n-k}}\rfloor\ modulo\ 2$. In C language you would of course use bitwise operations instead (>> and <<). – user3017842 Mar 12 '15 at 13:27
2

$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$.)

paw88789
  • 40,402
  • Thank you for the answer, it seems to work. However, I was hoping for a more straightforward solution in the decimal system. Do you think there is none? – zbr Mar 12 '15 at 11:54
  • The children of node labelled $n$ are $2n$ (left child) and $2n+1$ (right child)--this can be shown inductively. Going from $n$ to $2n$ corresponds to (right)-appending a $0$ to the binary representation of $n$; and going from $n$ to $2n+1$ corresponds to (right)-appending a $1$ to the binary representation of $n$. I think this is probably simplest (compared to trying to do something with the decimal representation of $n$). – paw88789 Mar 12 '15 at 12:18
0

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.

Daniel Donnelly
  • 21,342
  • Thank you for an answer, however, I think you're assuming too much. I don't want to change the structure of the tree in any way. The tree from my question may not be sorted, but it is structured and named in such a regular fashion that there just has to be a simple mathematical solution. Are you saying there is none? – zbr Mar 11 '15 at 16:00