ISRO CS 2023 Q.26: solution and answer

Official answer: DSource: ISRO's revised and final answer key of 16 February 2024

1. The inorder predecessor of a node is the key visited just before it in an inorder traversal (left subtree, node, right subtree). When the node has a left subtree, that key is the largest key in the left subtree.

2. Node $15$ has a left subtree rooted at $6$, so the predecessor is the maximum of that subtree.

3. The maximum of a binary search tree is found by following right children until none remains: $6\to 7\to 13$.

4. Node $13$ has only a left child ($9$) and no right child, so the walk stops at $13$. Every key in $13$'s subtree is at most $13$, so $13$ is the maximum of the left subtree of $15$.

5. Check with the full inorder sequence: $2,3,4,6,7,9,13,15,17,18,20$. The key immediately before $15$ is $13$.

6. The other options fail: $18$ lies in the right subtree of $15$, so it comes after $15$ in inorder; $7$ and $9$ are in the left subtree but are smaller than $13$, so they are not the last key visited before $15$.