Question

1. A certain Professor Amongus claims that the order in which a fixed set of ele- ments is inserted into a binary search tree does not matter—the same tree results every time. Give a small example that proves Professor Amongus wrong.

Answer 1

Solution :-

Basically we assume that all the numbers present in the binary search tree are distinct even if they happen to be same, they are placed in the same position.

Rules to construct a binary search tree :-

1. All the elements that are lesser than the root element will be present in the left side of the root or will be a part of the left child of the root.

2. All the elements that are greater than the root element will be present in the right side of the root or will be a part of the right child of the root.

According to the question, the professor claims that " the order in which a fixed set of elements is inserted into a binary search tree does not matter ".

This claim is not true, because the structure of the binary search tree totally depends on the order in which the elements are inserted in the BST.

Let's look into an example of a binary search tree containing the elements 50, 15, 62, 5, 20, 65.

According to the order let's construct the BST.

Let's enter the node with value 50 first.

Now the value of 15 is less than 50 so it will go to the left of 50.

Let's enter the node of 15.

Now let's enter 62, according to the rule.

After 62, let's enter 5.

Entering 20 this time.

Now, 65.

Here is the final structure of the tree.

If we change the structure of the tree and swap 15 with 20, then the order changes to 50, 20, 62, 5, 15, 65.

We will follow the same insertion rules with insertion of 50 first then 20, then 62, then 5 then 15 and in the end 65.

The final structure of the tree will look like :-

We can observe the two structures that we finally got before and after changing the order of the elements.

We found out that the structure of both the BST are different and hence we can say that the order in which the elements are arranged does matter.