0

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!!

ananya
  • 879
  • 1
  • 7
  • 14
  • Why does it have to be a binary search tree? Binary search tree searches the values. You're just doing indices. Note that how this data is stored is equivalent to a heap, which is a tree that is normally stored in an array because of this regular structure. Note that 6 = 2 * 3, and 3 is the parent of 6, and 6 is the left child of 3. Note also that 5 = 2 * 2 + 1 and 2 is the parent of 5, and 5 is the right child. Can you find the pattern relating the nodes on one level and their parent nodes? Now extend that for arbitrary levels. – alkasm Feb 16 '19 at 00:57
  • 1
    If it is a *complete* binary tree (you did not say if it is) this is easy enough as you can calculate the level and position and hence do the traversal. See https://stackoverflow.com/q/12359660/1256452 – torek Feb 16 '19 at 00:58
  • Ah yes, my suggestion hinges on the fact that @torek points out, which is that it is a complete tree (basically, that it fills out the levels from left to right before going down to the next level). Your example *is* a complete tree, but if it isn't, then the problem isn't well defined. – alkasm Feb 16 '19 at 00:59
  • @AlexanderReynolds Thank you for your reply! But I do not see how this solves the question. I mean given the index 9 and you start from the 1. How can you decide at each level to go left or right to reach to index 9. Thanks! – ananya Feb 16 '19 at 01:02
  • 1
    If you modify your diagram to write the indices in binary (as `1`, `10`, `11`, `100`, etc.), the pattern that Alexander Reynolds describes should be more obvious. – ruakh Feb 16 '19 at 01:06
  • 2
    9's parent is 4 (9 = 2 * [4] + 1). 4's parent is 2 (4 = 2 * [2] + 0). 2's parent is 1. So to get to 9, you go left to 2, left to 4, right to 9. With binary, 1001 (aka 9)'s parent is 100, and 1001 is on the right. 100s parent is 10, and 100 is on the left. 10's parent is 1, and 10 is on the left. – alkasm Feb 16 '19 at 01:07
  • Did you consider that since they asked you for an index they must mean an array implementation of a tree? If they passed you an index and want you to find the index why not... def reach_To_Index(root, index) : return index ? – Vic Feb 16 '19 at 04:15
  • 1
    @Vic The main idea they wanted me to implement is to write a recursive function that shows how to reach to the index. At each level you have to decide to go left or right. That what they wanted me to do. Once you reach to that index, then you can return the index, the data or do something else. But the main thing is how to get there and what is the condition at each level ? – ananya Feb 16 '19 at 05:02
  • Thanks @ananya that makes more sense. So I think you can say if(2j%2==0): go to left child else: go to right child. – Vic Feb 16 '19 at 15:52

1 Answers1

1
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
krisz
  • 2,686
  • 2
  • 11
  • 18