GATE CSE 2015 Set 1 | Question: 10

Question

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

1. $3, 5, 7, 8, 15, 19, 25$
2. $5, 8, 9, 12, 10, 15, 25$
3. $2, 7, 10, 8, 14, 16, 20$
4. $4, 6, 7, 9, 18, 20, 25$

• A. I and IV only
• B. II and III only
• C. II and IV only
• D. II only

Comments

Inorder traversal gives nodes in non-decreasing order

---

In $Inorder$ traversal first left node is printed then root node and finally right node.
$Left Node -> Root Node -> Right Node$

In a BST, $Left Node=< Root Node < Right Node$ Hence, Inorder always traverses the BST in ascending order.

---

It is unbelievable that GATE is asking such questions

---

Look it as a whole paper point of view. I did the same mistake thinking like this for JEE questions. Try to solve the whole set of 65 questions and then in that you won't feel the same about this question.

Answer 1

In order traversal of key are always in ascending order.

So, here I & IV th sequence  are in ascending order so Option A is Answer.

Comments

This is not quick, it's ONLY solution for this problem :D :)

Answer 2

option A is right .. chek for left root right rule

Comments

A...

Answer 3

Simply look for the sequences having ascending order, that's it!

You'll get the answer!