[FIXED] How to traverse this binary tree in O(log n) time?

Issue

I had an interview today and the question was:

Given this binary tree, write a function to reach to any given index in ONLY O(log n) time.

Note: The numbers in this binary tree are indices NOT values. Consider the values are empty.

The function accepts 2 parameters: The root and the index we want.

def reach_To_Index(root, index)

The tree exactly as he gave it to me

           1
        /     \
      2        3
     / \      /  \
   4    5    6    7
 /  \                
8    9

My answer was: I can do that if it is a Binary Search Tree, but his response was, it is not a Binary Search Tree, but you can use the modulus to reach to the answer!

My question is it possible? and if yes, could any one write this function please!!

Solution

def reach_to_index(node, index):
    if index == 1:
        return node

    power = 2**(int(math.floor(math.log(index, 2))) - 1)
    new_index = power + index % power

    if index < 3 * power:
        return reach_to_index(node.left, new_index)
    return reach_to_index(node.right, new_index)

Using the binary representation of the index:

def reach_to_index(node, index):
    for bit in bin(index)[3:]:
        node = node.left if bit == '0' else node.right
    return node

Answered By - krisz