Question

IN JAVA

Given a binary search tree, extract min operation finds the node with minimum key and then takes it out of the tree. The program can be C++/Java or C-style pseudocode. Do not use function call to either Min or delete done in the class. Write this from scratch. (No need to ensure AVL properties, just show it for a generic BST)

Node * extract min(Node * x) {

}

Answer 1

A binary search tree, extract min operation finds the node with minimum key and then takes it out of the tree. The program can be C++/Java or C-style pseudocode.

Explanation:

Your Explanation :

------------------------

In a BST, the lowest key is the leftmost node. So the algorithm is to move left as long as there is a left child, and return the node having no left child.

The pseudo code using c-style is as follows (using recursion):

Node * extract_min(Node * x) {

   /* Case 1: empty tree */

   if(x == NULL)

       return NULL;

   /* Case 2: this is the leftmost, i.e. lowest key */

   if(x->left == NULL)

       return x;

   /* Case 3 (recursive case): left subtree exists, recurse on it */

   return extract_min(x->left);

}

A non-recursive iterative version is as follows:

Node * extract_min(Node * x) {

   Node * n = x;

   if(x == NULL)

       return NULL;

   while(n->left != NULL)

       n = n->left;

   return n;

}