GATE 2017 CS (CS2) – Question 46

Programming and Data Structures · Trees and Binary Search Trees · 2 marks · Multiple choice

BST preorder is 12,8,6,2,7,9,10,16,15,19,17,20. Find its postorder.

2,6,7,8,9,10,12,15,16,17,19,20
2,7,6,10,9,8,15,17,20,19,16,12
7,2,6,8,9,10,20,17,19,15,16,12
7,6,2,10,9,8,15,16,17,20,19,12

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (B) 2,7,6,10,9,8,15,17,20,19,16,12

Explanation

Root 12 splits left keys below 12 from right keys above 12. The left subtree rooted at 8 has postorder 2,7,6,10,9,8. The right rooted at 16 has 15,17,20,19,16. Appending root 12 gives option B. Every subtree follows left, right, root.

More Trees and Binary Search Trees questions

GATE 2012 CS (CS1) Q57 – Height counts edges on the longest downward path. Fill B1 and B2.
GATE 2013 CS (CS1) Q17 – What is the tightest worst-case upper bound for inserting into a binary search tree with n…
GATE 2013 CS (CS1) Q53 – A BST has preorder 30,20,10,15,25,23,39,35,42. Find its postorder.
GATE 2011 CS (CS1) Q39 – An unlabelled binary-tree shape has n nodes and n distinct keys are supplied. In how many…
GATE 2010 CS (CS1) Q20 – In a binary tree with n nodes, every node has an odd number of descendants, counting…
GATE 2015 CS (CS2) Q23 – A binary tree T has 20 leaves. How many nodes have exactly two children?

All Trees and Binary Search Trees questions →