IAE Academy

GATE 2026 CS1 Q.62: solution and answer

GATE 2026 · CS1Q.62 · 2 marks · NAT

The following sequence corresponds to the preorder traversal of a binary search tree :

The position of the element 60 in the postorder traversal of is ______. (answer in integer)

Note: The position begins with 1.

See the question in the paper
GATE 2026 CS1 question 62Tap to open full size

Answer and solution

ANSWER

The position of element 60 in the postorder traversal of T is 7.

Official answer: 7Source: Official answer key, GATE 2026 CS1 (IIT Guwahati)

  1. Reconstruct the BST from preorder using the property: first element is the root; among the remaining elements, those less than the root form the left subtree's preorder, those greater form the right subtree's preorder — recursively.

  2. Root = 50. Left subtree preorder (values < 50): 25, 13, 40, 30, 47. Right subtree preorder (values > 50): 75, 60, 70, 80, 77.

  3. Left subtree: root 25; left of 25 = {13}; remaining 40, 30, 47 (all > 25) form the right-of-25 preorder: root 40, left = {30}, right = {47}. So left subtree = 25(13, 40(30, 47)).

  4. Right subtree: root 75; left-of-75 preorder is 60, 70 (both < 75): root 60, and since 70 > 60 it is the right child of 60, giving 60(-, 70); right-of-75 preorder is 80, 77 (both > 75): root 80, and since 77 < 80 it is the left child of 80, giving 80(77, -). So right subtree = 75(60(-, 70), 80(77, -)).

  5. Postorder (left, right, root) of the 25-subtree: postorder(13) = 13; postorder(40-subtree) = postorder(30), postorder(47), 40 = 30, 47, 40; so postorder(25-subtree) = 13, 30, 47, 40, 25.

  6. Postorder of the 75-subtree: postorder(60-subtree) = (nothing), 70, 60 = 70, 60; postorder(80-subtree) = 77, (nothing), 80 = 77, 80; so postorder(75-subtree) = 70, 60, 77, 80, 75.

  7. Full postorder of T = [13, 30, 47, 40, 25] + [70, 60, 77, 80, 75] + [50] = 13, 30, 47, 40, 25, 70, 60, 77, 80, 75, 50.

  8. Counting from position 1: 13(1), 30(2), 47(3), 40(4), 25(5), 70(6), 60(7), 77(8), 80(9), 75(10), 50(11). The element 60 is at position 7.

KEY IDEA

In a BST, a preorder listing splits uniquely at each node into (root, values less than root = left subtree preorder, values greater than root = right subtree preorder). Recursively rebuild both subtrees this way, then compute postorder (left, right, root) on the rebuilt tree.

WATCH OUT FOR

Trying to compute the postorder position of 60 without fully separating each subtree's preorder segment first — e.g. misplacing 70 as a left child of 75 instead of the right child of 60, or misplacing 77 as the right child of 75 instead of the left child of 80 — which shifts the final position count.

From the GATE 2026 CS1 paper. Every question of this paper · Download the full paper · All 26 Trees & heaps questions, with notes

More Trees & heaps questions