Consider a BST with n distinct values and height h. Let x be a value in this BST

Question

Consider a BST with n distinct values and height h. Let x be a value in this BST.

(a) Assume that x is not the largest value in the BST. How fast can you find the smallest value larger than x in the BST, in the worst case? You should find the best time complexity as a function of n and/or h.

(b) Assume that the BST has at least k values larger than x. How fast can you find the k smallest values larger than x, in the worst case?

For both parts, provide an algorithm and analyze its time complexity.

Explanation / Answer

a) The algorithm is as follows:

   We will start from the root.If the root is smaller, we will move to right child.If
   the root is bigger, we will move to left.At every node we have to make the move like
   that.For any node if its value is less than K , we will move to right otherwise
   we will move to left. While doing that we can.t move to left , when we want to and
   if we can't move to right when we want to, then that node will be the answer.As
   we are traversing down the tree along the height, the complexity will be O(log(n))

b) In this case we will follow the algorithm mentioned in a to find the smallest    number larger than x. The only difference will be this time we need to move as
   follows.
   If the node value is larger than k , we will move to the left and if the value is       lower we need to move to the right. Again the complexity will be same as in a).The
   extra thing we need to do will be to move up the tree (kind of backtraking) k nodes
   as we are looking for smallest k numbers larger than x.The complexity remains the
   same because there is not much impact of this activity on the overall complexity.

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.