The GATE Grind

GATE 2020 CS – Question 15

Programming and Data Structures · Trees and Binary Search Trees · 1 mark · Multiple choice

The preorder traversal of a binary search tree is 15, 10, 12, 11, 20, 18, 16, 19.

Which one of the following is the postorder traversal of the tree?

  1. 10, 11, 12, 15, 16, 18, 19, 20
  2. 11, 12, 10, 16, 19, 18, 20, 15
  3. 20, 19, 18, 16, 15, 12, 11, 10
  4. 19, 16, 18, 20, 11, 12, 10, 15

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (B) 11, 12, 10, 16, 19, 18, 20, 15

Explanation

Root 15 has left subtree 10 (right child 12, whose left child is 11). Its right subtree is 20 with left child 18, which has children 16 and 19. Postorder: 11, 12, 10, 16, 19, 18, 20, 15.