Suppose a binary search tree with 15 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 1, the largest element of the tree is stored at index ______________ .

GATE 2022 · Programming and Data Structures · Binary Search Tree · medium

Answer: The largest element is stored at index 15.

1. Identify the structure of the complete BST: With 15 nodes, this is a perfect binary tree (all levels completely filled). The height is 3 (0-indexed) or 4 levels total. Every internal node has exactly 2 children.
2. Find the rightmost node using heap indexing: In a BST, the maximum is the rightmost node. Starting from root at index 1, always follow the right child: - Root: index 1 - Right child of 1: index 2*1+1 = 3 - Right child of 3: index 2*3+1 = 7 - Right child of 7: index 2*7+1 = 15 Node at index 15 has no children (15*2 = 30 > 15 and 15*2+1 = 31 > 15), so it is a leaf.
3. Confirm index 15 is the rightmost leaf: In the heap array representation of a 15-node perfect binary tree: - Level 0 (root): index 1 - Level 1: indices 2-3 - Level 2: indices 4-7 - Level 3 (leaves): indices 8-15 The rightmost leaf is at index 15. Since this is a BST, the largest element is stored there.