# Traversing through a binary tree

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?

• Hint: express each number in binary. Mar 11 '15 at 15:37
• @vadim123: I have tried that and it hasn't provided any results. Could you elaborate more, please?
– zbr
Mar 11 '15 at 15:55
• Can you see that the child of a node $i$ simply $2i$ (left) and $2i+1$ (right)? Mar 11 '15 at 16:03
• @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.
– zbr
Mar 11 '15 at 16:08
• 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. Mar 11 '15 at 16:24

## 3 Answers

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.

• 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 <<). Mar 12 '15 at 13:27

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

• 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$). Mar 12 '15 at 12:18

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.

• 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