Project ForgeWhich 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
- I and IV only
- BII and III only
- CII and IV only
- DII only
Explanation
The inorder traversal of a BST always visits keys in strictly increasing order — so any candidate sequence must itself be sorted ascending. Sequence I (3,5,7,8,15,19,25) is sorted — valid. Sequence II has 12 followed by 10 — not sorted, invalid. Sequence III has 10 followed by 8 — not sorted, invalid. Sequence IV (4,6,7,9,18,20,25) is sorted — valid. So I and IV only.
Source: GATE CS 2015 (Session 1 / 7th Feb Shift 1) (2015)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.