Question 1 |

Suppose a binary search tree with 1000 distinct elements is also a complete binary tree. The tree is stored using the array representation of binary heap trees. Assuming that the array indices start with 0, the 3rd largest element of the tree is stored at index _______.

510 | |

999 | |

509 | |

501 |

Question 1 Explanation:

Question 2 |

A binary search tree T contains n distinct elements. What is the time complexity of picking an element in T that is smaller than the maximum element in T?

\Theta(n\log n) | |

\Theta(n) | |

\Theta(\log n) | |

\Theta(1) |

Question 2 Explanation:

Question 3 |

What is the in-order successor of 15 in the given binary search tree?

18 | |

6 | |

17 | |

20 |

Question 3 Explanation:

Question 4 |

The preorder traversal of a binary search tree is 15,10,12,11,20,18,16,19. Which one of the following is the postorder traversal of the tree?

10,11,12,15,16,18,19,20 | |

11,12,10,16,19,18,20,15 | |

20,19,18,16,15,12,11,10 | |

19,16,18,20,11,12,10,15 |

Question 4 Explanation:

Question 5 |

The pre-order transversal of a binary search tree is given by 12, 8, 6, 2, 7, 9, 10, 16, 15, 19,
17, 20. Then the post-order traversal of this tree is:

2,6,7,8,9,10,12,15,16,17,19,20 | |

2,7,6,10,9,8,15,17,20,19,16,12 | |

7,2,6,8,9,10,20,17,19,15,16,12 | |

7,6,2,10,9,8,15,16,17,20,19,12 |

Question 5 Explanation:

There are 5 questions to complete.