-
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?
-
- 7 5 10 3 2 4 6 8 9
- 0 2 4 3 1 6 5 9 8 7
- 0 1 2 3 4 5 6 7 8 9
- 9 8 6 4 2 3 0 1 5 7
- 7 5 10 3 2 4 6 8 9
Correct Option: C
We can solve it in shortcut that the first given element in 7, so we need to choose that particular option in which 7 is at the right place i.e. all the elements on its left should be smaller than it & all the elements on the right should be equal & greater than it.
So this rule is followed in option (c) only. To make in order of a binary search tree.
(i) Start with the root node.
(ii) Scan its left subtree,
(iii) If the node in subtree has any left child then store the node in stack & repeat this step for its left child unit no. left child of any node.
(iv) If leaf reached then print the node & pop the stack, print the poped value.
(v) Check its right subtree & repeat step (III) for it.
(vi) When stack empty then stop
So here inorder is 0 1 2 3 4 5 6 7 8 9. Actually a fact can be remembered that inorder traversal of a BST leads to a sorted sequence of elements. Hence (c) is correct option.
