GATE CS 2026 Set 1 Q52 — Searching, Sorting, Hashing

To find the position of the element $60$ in the postorder traversal, we first reconstruct the Binary Search Tree (BST) from the given preorder traversal: 50, 25, 13, 40, 30, 47, 75, 60, 70, 80, 77.

In a BST, the first element of the preorder traversal is the root, elements smaller than the root form the left subtree, and elements larger form the right subtree. Following this recursively, we reconstruct the tree:

• Root: $50$
  • Left Subtree (elements < 50): Preorder 25, 13, 40, 30, 47
    • Root is $25$. Left child is $13$. Right subtree is 40, 30, 47 (Root $40$, Left $30$, Right $47$).
  • Right Subtree (elements > 50): Preorder 75, 60, 70, 80, 77
    • Root is $75$. Left subtree is 60, 70 (Root $60$, Right $70$). Right subtree is 80, 77 (Root $80$, Left $77$).

Now, we find the postorder traversal ($\text{Left} \to \text{Right} \to \text{Root}$):

1. Postorder of Left Subtree (rooted at 25): $13, 30, 47, 40, 25$
2. Postorder of Right Subtree (rooted at 75):
   • Left child (rooted at 60): $70, 60$
   • Right child (rooted at 80): $77, 80$
   • Combined: $70, 60, 77, 80, 75$
3. Postorder of entire tree (rooted at 50):
   $13, 30, 47, 40, 25, 70, \mathbf{60}, 77, 80, 75, 50$

Counting the positions from left to right (1-indexed):

Thus, the position of the element $60$ is $7$.