Question

21 : Suppose the numbers 7,5, 1, 3, 6, 0, 9,4 are
inserted in that order into an initially empty binary
search tree.
What is the in-order traversal sequence of the
resultant tree?
​

Answer 1

Given:

Given numbers are 7, 5, 1, 3, 6, 0, 9, 4.

To find:

We should find the in-order traversal sequence of the resultant tree.

Solution:

Before solving the question, we should know the meaning of in-order traversal.

• The meaning of traversing means visiting every node in the binary search tree.
• There are three types of tree traversal method:

1. Pre - order traversal
2. In - order traversal
3. Post - order traversal

In - order traversal:

In this method, first visit the nodes in the left subtree and then go to the root node and then visit the nodes in the right subtree.

First, draw the binary search tree with given numbers.

(Refer the attached image for binary search tree)

Now, perform in - order traversal i.e., go to left, then root, then right.

So, the in - order traversal sequence is 0, 1, 3, 4, 5, 6, 7, 9.

Therefore, the required sequence is 0, 1, 3, 4, 5, 6, 7, 9.