IIT Kanpur

Question

There is a height-balanced tree T storing n elements. The greatest element smaller than x in T is called the predecessor of s in T. Given any positive number k, we wish to compute k predecessors of x in T. What is the time complexity of the best algorithm that can do this task?

A. O(k + log n)

B. O(k log n)

C. O(log(n + k))

D. O(n + k)

Comments

LEt us talk about AVL tree as it is height balanced tree.Now i am not sure if height balanced always give sorted inorder,but i think yes from options we have some log terms.

We need to computer K predecessors of a node.Let us use following algo:-

$1.$ Find the x,since height balanced it can done in$O(logn)$

$2.$ Predecessor of X will lie in left subtree of X only.As question does not say which K nodes,so we can assume any k nodes.I mean let us say i have 1-20 elements.Now if i find ,k=5,predecessor of X=15,then for 15 there will be 14 predecessor 1-14,i can take any 5(K) from that.

It can be done O(k)

SO it should be logn+k

---

Shouldn't k predecessors imply that we have to take the greatest element then the second greatest, and so on upto kth greatest element? The question does say that a predecessor is the greatest element smaller than x.

---

Yes you are correct  Let me think again

---

You can apply reverse in order in step 2 which will give you decreasing order. Just visit Right root left.

---

I didn't get the second step, and what will be the time complexity then?

---

why not O(klogn)

---

How?

---

@srestha ,please provide your solution.

---

1 predecessor find we can do in logn times

k predecessor we can find in klogn

rt?