What is the index of the right child of a node at index i in an Array representation of a Max heap? Assume the cell at index 0 is empty.

State and explain the best case time complexity of the following:

• One delete operation on a balanced BST [2.5 marks]
• One delete operation on an unbalanced BST [2.5 marks]

Define your input variable in terms of the number of items in the BST. No explanation no marks.

Given a subtree rooted by node X in a BST, explain in one line how to find the node with the minimum value in this subtree. [2 marks]

What is the best and worst case time complexity of the get_minimum method a BST? Base your answer on the total number of nodes in the BST. No explanation no marks. [3 marks]

State and explain the worst case time complexity of the HeapSort algorithm. Make sure to inlcude both heap methods in your analysis. No explanation no marks.

def heapsort(items):
    res = ArrayR(len(items))
    heap = ArrayMaxHeap.heapify(items)
    for i in range(len(items)):
        res[i] = heap.extract_max()
    return res

Consider the following Binary Search tree

       10
    ___|___
   |       |
   5       15
  _|_     _|_
 |   |   |   |
 3   7  12  20

What is the result of an inorder traversal of the given BST?

How does Pre-Order traversal work in a Binary Tree?

Given the max heap below, explain the steps needed to delete the maximum element.

(Explain the steps on this particular tree, and use its values in your explanation).

       80  
     ___|___  
    |       |  
    30      70  
   _|_     _|_  
  |   |   |   |  
  20  10  50  40  
 _|  
|
5

What is the best-case and worst-case complexities of 'delete' in an unbalanced BST where N is the number of nodes in the tree?

Linear probing causes primary clustering while quadratic probing causes secondary clustering. Compare the two types of clustering and explain why Secondary clustering is less severe than primary clustering.

Consider when quicksort selects a random pivot in O(1) time.

State and explain the worst case time complexity of quicksorting list of unique values. No explanation no marks.