The GATE Grind

GATE 2015 CS – Question 17

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

Which of the following is/are correct inorder traversal sequence(s) of binary search tree(s)?

I. 3, 5, 7, 8, 15, 19, 25

II. 5, 8, 9, 12, 10, 15, 25

III. 2, 7, 10, 8, 14, 16, 20

IV. 4, 6, 7, 9, 18, 20, 25

  1. I and IV only
  2. II and III only
  3. II and IV only
  4. II only

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (A) I and IV only

Explanation

The inorder traversal of a binary search tree is always in increasing order. Sequences I and IV are increasing. Sequence II has 12 before 10 and sequence III has 10 before 8, so those are not sorted.