Test by Bikram | Mock GATE | Test 2 | Question: 32

Question

Suppose that six keys are inserted into an unbalanced binary search tree in the following order: $4, 6, 3, 8, 2$, and $5$.

Then which of the following statements is/are correct statement?

1. Finding a key in the resulting tree requires examining $1, 2$, or $3$ nodes.
2. The resulting tree has equal numbers of interior and leaf nodes.
3. The key $7$ can now be inserted without adding another level to the tree.

• A. I and II only
• B. I and III only
• C. II and III only
• D. I, II, and III

Comments

initially the tree was empty?

---

where did element 1 come from?

---

@Gokhale

Here what you mis-understood as element 1 is actually number of comparisons.

Option I want to say  to find a key in the resulting tree requires 1 comparisons or 2 comparisons or 3 comparisons ?

---

@Ritwik

yes, the tree is empty initially , we need to build that tree using 4, 6, 3, 8, 2, and 5.

Answer 1

The resulting tree looks like below tree :

   4

  /  \

 3    6

/     /   \

2   5     8

 

 

 

Finding 4 now takes one comparison (with the root), finding 3 and 6 take two comparisons, and finding the other nodes takes three comparisons. Hence option I is correct .

There are three leaf nodes and three interior nodes. Option II is correct .

If 7 is inserted, it will go onto a new level, as the left child of 8. This makes option III false .