GATE CS 2026 Set 1 Q.62: Binary Trees, Binary Search Trees and Balanced Trees

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)

Note: The position begins with 1.

Your answer

Official answer and solution

Official answer: 7
From: Official GATE 2026 answer key

Solution

Reconstruct the BST $T$ from its preorder sequence by partitioning around each root, then write its postorder sequence.

In a BST, the first element of the preorder sequence is the root, all smaller elements form the left subtree, and all larger elements form the right subtree:

Root $= 50$ $= 50$
- Left subtree of $50$ : $\text{Pre} = [25, 13, 40, 30, 47]$ ( $5$ nodes) $\implies \text{Post} = [13, 30, 47, 40, 25]$
- Right subtree of $50$ $50$ : $\text{Pre} = [75, 60, 70, 80, 77]$ $Pre = [75, 60, 70, 80, 77]$ with root $75$ $75$ :
  - Left subtree of $75$ : $\text{Pre} = [60, 70]$ (root $60$ , right child $70$ ) $\implies \text{Post} = [70, 60]$
  - Right subtree of $75$ : $\text{Pre} = [80, 77]$ (root $80$ , left child $77$ ) $\implies \text{Post} = [77, 80]$

Concatenating gives the full postorder traversal of $T$ :

13, 30, 47, 40, 25, 70, \mathbf{60}, 77, 80, 75, 50

The element $60$ is at position 7.

Final answer

Common trap

Listing 60 before its right child 70 in postorder (which would give position 6).

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2026 Computer Science and Information Technology - Session 1 (CS1)
Question: 62 of 65
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source