Past gate question modification(Gate 2003,Q.23)

Question

If in this question, if we were asked to find the nth smallest number, then what would have been the answer?

Comments

O(n)

---

But how brother?

---

Lets start from the root. The number of comparisons to get smallest number among root and its 2 children is 3. So O(1) time.

Secondly, to get 7th smallest number we need constant number of comparison. Hence again O(1).

Now lets extend this comparison to n levels. In that that case we might have to use a hash table and the complexity would rise up to O(n).

Hope it helps..

---

What an answer brother. Thanks

Answer 1

I think (n logn)

Comments

How?