Question

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 \(\underline{\hspace{1cm}}\).

Hint:

In a complete binary tree, the largest elements in a heap are usually at the root or near it. For a binary heap, the kth largest element is found in the rightmost leaf nodes.

Answer 1

Correct Answer: 509

In a complete binary tree, elements are stored in an array in level-order traversal. The left child of an element at index \(i\) is at index \(2i + 1\), and the right child is at index \(2i + 2\). The largest element of the tree will be at the root (index 0), and the second largest will be one of its children, and so on.
The third largest element is the element that is stored at index: \[ \boxed{509}. \]