GATE 2026 CS (CS1) – Question 62
The following sequence corresponds to the preorder traversal of a binary search tree $T$:
$$50, 25, 13, 40, 30, 47, 75, 60, 70, 80, 77$$
The position of the element 60 in the postorder traversal of $T$ is ______. (answer in integer, position begins with 1)
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: 7
Explanation
In any Binary Search Tree (BST), the in-order traversal visits keys in ascending order.
Sorting the given elements gives the in-order traversal:
$$\text{In-order}: 13, 25, 30, 40, 47, 50, 60, 70, 75, 77, 80$$
Reconstructing the BST from preorder and in-order:
- Root is 50.
- Left subtree has keys $< 50$: $\{13, 25, 30, 40, 47\}$. Preorder: $25, 13, 40, 30, 47$.
- Subtree root is 25.
- Left child of 25 is 13.
- Right child of 25 is 40, with left child 30 and right child 47.
- Right subtree has keys $> 50$: $\{60, 70, 75, 77, 80\}$. Preorder: $75, 60, 70, 80, 77$.
- Subtree root is 75.
- Left child of 75 is 60, with right child 70.
- Right child of 75 is 80, with left child 77.
Now compute the postorder traversal (Left, Right, Root):
1. Left subtree of 50:
- Left of 25: 13
- Right of 25: 30, 47, 40
- Node 25
$\implies$ Sequence: $13, 30, 47, 40, 25$
2. Right subtree of 50:
- Left of 75: (Left: null, Right: 70, Root: 60) $\implies 70, 60$
- Right of 75: (Left: 77, Right: null, Root: 80) $\implies 77, 80$
- Node 75
$\implies$ Sequence: $70, 60, 77, 80, 75$
3. Root 50.
Combining into full postorder traversal:
1st: 13
2nd: 30
3rd: 47
4th: 40
5th: 25
6th: 70
7th: 60
8th: 77
9th: 80
10th: 75
11th: 50
The element 60 appears at position 7.
The correct answer is 7.