A Rational Sequence (Take 3)

This problem defines a labeling of a binary tree and then asks you to identify where in a binary tree a given node falls based on its labeling.

By inspection, we can see that for a given label p/q, if p>q, it means that we must be the RIGHT hand child of our parent, and if p<q, we must be the LEFT hand child. We can apply this rule recursively to find the label of our parents until we reach the root of the tree.

Once we have derived the sequence of L/R hand turns it takes to reach our node, we can come up with our index in the tree.

If we have determined we are Y levels deep in the tree, obviously we add 2^Y-1 to our index to account for the levels above (HINT: sum(2^x) == 2^(x+1)-1). Then we just have to figure out how far we are from the "left" hand side of the tree. Fortunately this is relatively simple to calculate since we know the level we exist at (lets call it L). If we take a right hand turn at the root, we know we have L "extra" nodes to our left. If we take a turn at level 1, we have L/2 extra...etc.

extra = sum(L/2^(x+1)*right_at_level(x))

So if we turn right at level x, we have to add L/2^(x+1) to our "extra. This makes sense since if we turn right at level 0, we have to add L/2, or L/2^(0+1).