interview questions related to binary trees

      (a)    Given a BST with n ≥ m keys, what is the quickest time, in Big-O, in which you can find the m^th smallest key. For example, if the keys stored in the tree are 10, 20, 35, 60, 70, then for m=3, we have the third smallest key, which is 35.  How will you do it? (Don’t write code, just describe the method and state any assumptions you make).  Give the time complexity in terms of m and n.  

    

     SOLUTION

I will accept any reasonable answer here.  Some examples of answers given by students:

a. O(m)   if you have a BST skewed to the right then the smallest key is at the root node.

b. O(log n + m)  if you have a balanced BST then do an inorder traversal and stop immediately as soon as the mth key is printed.  To reach the smallest key you need to traverse O(log n) nodes and from their you need an additional m traversals.

    (b)   We wish to sort an array of numbers. This is what we do: Insert all elements one by one into a binary search tree. Repeatedly find and remove the minimum element from the tree and place it at the next location in the array. When the tree is empty, array will be sorted. What are the best and worst asymptotic running times/time complexity for this algorithm, on n numbers?  
SOLUTION

Worst case in case of a skewed tree:  O(n²)

Best case in case of a balanced/complete BST: O(n log n)

    (c)    If we replace the BST in (d) with a binary heap, how will that affect the running time?      

Always O(n log n) as the heap is a complete tree

     (d)   If we were to store a binary MinHeap in a linked tree, rather than an array, how will it affect the asymptotic running times/time complexity of the functions: getMin, deleteMin and insert? Based on your answer, explain why we choose to store heaps in arrays instead?  You can assume that we know the size of the heap in advance.       
SOLUTION

For the heap, whether it is a linked or an array structure, the following always hold:

getMin: O(1)

deleteMin: O(log n)

insert: O(log n)

Normally we use the array implementation so that we don’t need to store extra pointers and it is easier to implement using arrays.

 (e)    Given an ordered doubly linked list with n keys and head and tail pointers, you want to convert it into a separate BST. What’s the quickest asymptotic time/running time required to accomplish this task and why?   

SOLUTION

O(n) as we can start the traversal from the head or tail and build a skewed BST.