quickest way to find out if an element is in the left or right subtree

Question

If a binary tree is constructed as follows

• the root is 1
• the left child of an element n is 2*n
• the right child of an element n is (2*n)+1

if I get a number n, what's the quickest way to find out if it's in the left or right subtree of the root? Is there some easy-to-determine mathematical property of the left subtree?

note: this is NOT a homework question, though it is part of a bigger algorithmic problem I'm trying to solve.

Answer 1

Consider the numbers in binary. Each child will be the parent number with a 0 or 1 appended to it depending on whether it is left or right.

This means that everything to the left of the root will start 10 in binary and anything to the right will start 11 in binary.

This means that you should be able to work out which side it is on just using some shift operations and then some comparisons.

I should note that I don't know if this is the most efficient method but it is a easy to determine mathematical property of the left subtree.

As noted by others the consequence of the 0 or 1 appendation means that each digit encodes the path through the subtree. The first 1 represents the root of the tree and from then on a 0 will mean taking the left branch at that point and a 1 will mean taking the right branch.

Thus binary 1001101 would mean left, left, right, right, left, right.

An obvious consequence of this is that the number of binary digits will determine exactly how deep in the tree that number is. so 1 is the top (1st) level. 10 would be at the second level (one choice made). my example 1001101 would be at the 7th level (six choices made). I should note that I'm unfamiliar with Binary tree terminology so not sure if the root would usually be considered the first or zeroth level which is why I am being explicit about number of choices made too.

One last observation in case it hasn't already been observed is that the numbers will also be assigned counting from top to bottom, left to right. So the first level is 1. The next is 2 on the left, 3 on the right. The level below that will go 4, 5, 6, 7 and then the row below that 8, 9, 10, 11, 12, 13, 14, 15 and so on. This isn't any more useful mathematically but if you are trying to visualise it may well help.

Answer 2

Following from Chris' observation, there's a very simple rule: Let x be the node you are looking for. Let S be the binary representation of x. Then the digits in S after the first from most significant tell you the path from the root: 0 means go left, 1 means go right.

Example: x = 27₁₀ = 11011₂, so we need to go right, left, right, right to get there (the leading 1 is ignored).

The reason why this is true is that if you go right, you multiply by 2 (binary left shift by 1) and add a 1, so you are essentially appending a 1. Conversely, if you go left, you append a 0.