Suppose a binary search tree with 1000 distinct elements is also a complete…
2022
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_____________.
Attempted by 98 students.
Show answer & explanation
Correct answer: 509
Key insight: in a BST the maximum is reached by repeatedly following right children; with a 0-based array representation the right child of index i is 2i+2 and the parent is floor((i-1)/2).
Find the maximum (largest) element by following right children from the root (index 0): indices encountered are 0 → 2 → 6 → 14 → 30 → 62 → 126 → 254 → 510. The next right child would be at index 1022, which is beyond the array (n−1 = 999), so the maximum is at index 510.
The 2nd largest is the in-order predecessor of the maximum. Since the maximum (index 510) has no left child, its predecessor is its parent: index floor((510-1)/2) = 254.
The 3rd largest is the predecessor of the node at index 254. That node has a left child at index 509 (2·254+1 = 509). The rightmost node in that left subtree is the node at index 509 itself (its right child would be at 1020, beyond the array).
Therefore the 3rd largest element is stored at index 509.