GATE CSE 2003 | Question: 19, ISRO2009-24

Question

Suppose the numbers $7, 5, 1, 8, 3, 6, 0, 9, 4, 2$ are inserted in that order into an initially empty binary search tree. The binary search tree uses the usual ordering on natural numbers. What is the in-order traversal sequence of the resultant tree?

• A. $7 \ 5  \ 1 \ 0 \ 3 \ 2 \ 4 \ 6 \ 8 \ 9$

• B. $0 \ 2 \ 4 \ 3 \ 1 \ 6 \ 5  \ 9  \ 8  \ 7$

• C. $0 \ 1 \ 2 \ 3 \ 4 \ 5 \ 6 \ 7 \ 8 \ 9$

• D. $9 \ 8 \ 6 \ 4  \ 2  \ 3 \ 0 \ 1 \ 5 \ 7$

Comments

Inorder traversal on BST gives sequence in increasing order(not just Sorted Order)

so Answer is C

---

The binary search tree uses the usual ordering on natural numbers.

What’s the use of mentioning above statement in question?

---

The binary search tree uses the usual ordering on natural numbers.

 

What’s the use of mentioning above statement in question?

Meaning the elements greater and equal to the root go to the right and the elements less than the root go to the left. 

 

Answer 1

In-order traversal returns the elements in ascending (smallest to largest) order.

Therefore, correct option C

Answer 2

Inorder traversal

1. First, visit all the nodes in the left subtree
2. Then the root node
3. Visit all the nodes in the right subtree

Answer 3

Inorder traversal on BST gives sequence in increasing order(not just Sorted Order)

so Answer is C