The pre-order traversal of a binary search tree is given by 12, 8, 6, 2, 7, 9, 10, 16, 15, 19, 17, 20. Then the post-order traversal of this tree is:
Topic-wise GATE CS PYQs with verified steps
GATE CSE 2017 Set 2 · Q36
Time
Select one answerSingle correct
Solution
Official answer: B) 2, 7, 6, 10, 9, 8, 15, 17, 20, 19, 16, 12
Binary Search TreesFor a Binary Search Tree (BST), the in-order traversal is always in ascending sorted order.
Given the pre-order traversal: Pre-order:
Sorting the elements gives the in-order traversal: In-order:
The root of the tree is the first element of the pre-order traversal: 12.
In the in-order traversal, elements to the left of are (Left Subtree) and to the right are (Right Subtree).
Reconstructing the Left Subtree (Root = ):
Left of : (Pre-order: ; Root = , Left child = , Right child = ). Post-order: .
Right of : (Pre-order: ; Root = , Right child = ). Post-order: .
Post-order of left subtree: .
Reconstructing the Right Subtree (Root = ):
Left of : . Post-order: .
Right of : (Pre-order: ; Root = , Left child = , Right child = ). Post-order: .
Post-order of right subtree: .
Combining Left Subtree, Right Subtree, and Root gives the overall post-order traversal: .
Therefore, option B is correct.
Try the question first, then check your work.
Examiner trap
Recall that the in-order traversal of any BST contains its elements in strictly sorted ascending order. Use the root from pre-order to split the in-order into left and right subtrees recursively.
This Binary Search Trees previous year question is Q36 of the GATE CSE 2017 Set 2 paper. Find more GATE CSE PYQs on Binary Search Trees in Programming and Data Structures, or browse all GATE CSE PYQs.
Free diagnostic
Take the 20-minute diagnostic: the 3 topics that cost you the most marks, and a rank range. Or sit 5 related Binary Search Trees PYQs now with no account.
An official question by email at 7 AM IST, with a link to its verified solution. Unsubscribe in one click.
Binary Search Trees has 21 GATE CSE PYQs across 17 papers from 2011 to 2026. 6 of them are 2-mark MCQs like this one, and it is the only one in GATE CSE 2017 Set 2.
How GATE tests Binary Search TreesIndependent practice explanation verified by the GateAI team. GATE is conducted by the IITs; question text follows the official paper.