BST largest key less than k and at a depth not less than x-CodePudding

I post this question just for curiosity and it's not homework. It was a question for one of my exams, I've graduated 8 years ago.

The problem is this:

Given a BST and two positive integers x and k, design an efficient recursive algorithm that deletes from the BST the node that contains the largest key less than k, and which is located at a depth not less than x.

The use of global variables or parameters passed by reference is not allowed.

I've solved the problem, but the teacher said that I've not used BST properties. The solution I provided was this:

Algo(T, x, k){
  temp = funz(T, x, k, 0);
  if(temp != NIL)
    T = delete(T, temp[k]); // standard delete algo
  return T;
}

Funz(T, x, k, dis) {  
  l= NIL;
  r = NIL;
  if(T = NIL)
    return T;
  if(dis < x){
    l = Funz(T->sx, x, k, dis   1);
    r = Funz(T->dx, x, k, dis   1);
    return Max(l, r); // return the maximum key nil otherwise
  }
  else
    return Predecessor(T, k); // standard predecessor algo
}

I know that the key must be located in some areas of the tree, so we can exclude some part of the tree, but the limit of the depth confuses me.

Someone can help?

CodePudding user response：

Indeed, your algorithm does not use the property of binary search trees.

The idea is to first find a candidate node without taking the depth requirement into account. If the depth of that node is fine, then return it. Otherwise look in the left-subtree of that node to find a deeper candidate node. If also that fails, backtrack.

Here is how your Funz function would look:

function Funz(T, x, k, depth) {
  if (T == NIL)
    return NIL;
  if (T->data >= k) // Too great. Look among lesser values
    return Funz(T->left, x, k, depth   1);
  // We have a candidate (but depth could still be an issue)
  // Try to improve (get closer to k)
  improved = Funz(T->right, x, k, depth   1);
  if (improved != NIL) // Found an improvement
    return improved;
  // No improvement found
  if (depth >= x) // Base case
    return T;
  // Not deep enough. Try lesser value
  return Funz(T->left, x, k, depth   1);
}