Question

How many comparisons are needed to locate or to addeach of these wordsin the search tree for Exercise 1, starting fresh each time?

a) pear

b) banana

c) kumquat

d) orange

Short answer

a) 3

b) 1

c) 4

d) 5

Step-by-step solution

Firstly, Use the whole binary search tree from the exercise 1.

From the exercise 1,

We get,

Now find the how many comparisons are needed to locate or to add pear word in the tree.

The word Pear is in the binary tree. Compare the word Pear with the root banana in the search tree. Pear is greater than banana. then, move to the right and secondly compare with Peach but pear is greater than peach so move to right. On this the word peach is located.Hence, the number of comparisons to locate the word pear is 3.

Now find the how many comparisons are needed to locate or to add banana wordin the tree.

The word Banana is in the binary tree. And in the search tree, banana is the root.

Hence, the number of comparisons to locate the word Banana is1.

Now find the how many comparisons are needed to locate or to add Kumquat wordin the tree.

The word Kumquat is in the binary tree. Compare the word Kumquat with the root banana in the search tree. Kumquat is greater than banana. So, move to the right and secondly compare with Peach, Kumquat is less than peach so move to left. At third compare with the word coconut, Kumquat is greater than coconut so move to the right and compare with Mango. But Kumquat is less than Mango so moves to left. As there is no other word to compare, fix the position of Kumquat.

Hence, the number of comparisons to locate the word Kumquat is 4.

Now find the how many comparisons are needed to locate or to add orangewordin the tree.

The word Orange is in the binary tree. Compare the word Orange with the root banana in the search tree. Orange is greater than banana.

So, move to the right and secondly compare with Peach, Orange is less than peach so move to left.

At third compare with the word coconut, Orange is greater than coconut so move to the right and compare with Mango. The word Orange is greater than Mango so moves to right. Compare with the word papaya, but the word orange is less than papaya, so move to the left. As there is no other word to compare, fix the position of Orange.

Hence, the number of comparisons to locate the word Orange is 5.