1
$\begingroup$

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?

$\endgroup$
5
  • $\begingroup$ Hint: express each number in binary. $\endgroup$
    – vadim123
    Mar 11 '15 at 15:37
  • $\begingroup$ @vadim123: I have tried that and it hasn't provided any results. Could you elaborate more, please? $\endgroup$
    – zbr
    Mar 11 '15 at 15:55
  • $\begingroup$ Can you see that the child of a node $i$ simply $2i$ (left) and $2i+1$ (right)? $\endgroup$
    – zed111
    Mar 11 '15 at 16:03
  • $\begingroup$ @zed111: Yes, I can see that, however I don't know how that helps in figuring out where to go from 1 if I want to reach 6. $\endgroup$
    – zbr
    Mar 11 '15 at 16:08
  • $\begingroup$ The entries in a level are $2^i$ to $2^{i+1}-1$. You can figure out where to go from the root at least. $\endgroup$
    – zed111
    Mar 11 '15 at 16:24
2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – zbr
    Mar 12 '15 at 11:54
  • $\begingroup$ 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 <<). $\endgroup$ Mar 12 '15 at 13:27
2
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$
    – zbr
    Mar 12 '15 at 11:54
  • $\begingroup$ 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$). $\endgroup$
    – paw88789
    Mar 12 '15 at 12:18
0
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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? $\endgroup$
    – zbr
    Mar 11 '15 at 16:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.