Question

Write pseudo code for the following parts of class BinarySearchTree:

a) find(x)

b) contains(x)

c) add(x)

d) remove(x)

e) splice(x)

f) min()

g) max()

h) pred()

i) succ()

j) floor()

k) ceil()

Answer 1

Pseudo code:

a) Find(x)

if (root == Null or root key == key)

  Then return root

if root key is greater than key

   Then search on the right child

else

    Search the key on the left child 



b) contains(x)

Compare if the item is equal to the value: 

if yes:

        return true;

else if:

       chek if (left! = null) left.contains(item);

      check if (right!= null)  right.contains(item);

return false;





c) Add(x)

 if (node == NULL) return newNode(key);

  

    /* Otherwise, recur down the tree */

    if (key < node->key)

        node->left  = insert(node->left, key);

    else if (key > node->key)

        node->right = insert(node->right, key);   

  

    /* return the (unchanged) node pointer */

    return node;



d) remove(x):


 if (root == NULL) return root;

  

    // If the key to be deleted is smaller than the root's key,

    // then it lies in left subtree

    if (key < root->key)

        root->left = deleteNode(root->left, key);

  

    // If the key to be deleted is greater than the root's key,

    // then it lies in right subtree

    else if (key > root->key)

        root->right = deleteNode(root->right, key);

  

    // if key is same as root's key, then This is the node

    // to be deleted

    else

    {

        // node with only one child or no child

        if (root->left == NULL)

        {

            struct node *temp = root->right;

            free(root);

            return temp;

        }

        else if (root->right == NULL)

        {

            struct node *temp = root->left;

            free(root);

            return temp;

        }

  

        // node with two children: Get the inorder successor (smallest

        // in the right subtree)

        struct node* temp = minValueNode(root->right);

  

        // Copy the inorder successor's content to this node

        root->key = temp->key;

  

        // Delete the inorder successor

        root->right = deleteNode(root->right, temp->key);

    }

    return root;


f) Min()

/* loop down to find the leftmost leaf */

while (current->left != NULL) 

{ 

    current = current->left; 

} 

return(current->data); 


g)Max:

 if (root == NULL)

      return INT_MIN;

  

    // Return maximum of 3 values:

    // 1) Root's data 2) Max in Left Subtree

    // 3) Max in right subtree

    int res = root->data;

    int lres = findMax(root->left);

    int rres = findMax(root->right);

    if (lres > res)

      res = lres;

    if (rres > res)

      res = rres;

    return res;



h) Pred():
if (root == NULL)  return ; 
  
    // If key is present at root 
    if (root->key == key) 
    { 
        // the maximum value in left subtree is predecessor 
        if (root->left != NULL) 
        { 
            Node* tmp = root->left; 
            while (tmp->right) 
                tmp = tmp->right; 
            pre = tmp ; 
        } 
  
        // the minimum value in right subtree is successor 
        if (root->right != NULL) 
        { 
            Node* tmp = root->right ; 
            while (tmp->left) 
                tmp = tmp->left ; 
            suc = tmp ; 
        } 
        return 


i)Succ():
 if (root == NULL) 
        return; 
  
    // Search for given key in BST. 
    while (root != NULL) { 
  
        // If root is given key. 
        if (root->key == key) { 
  
            // the minimum value in right subtree 
            // is predecessor. 
            if (root->right) { 
                suc = root->right; 
                while (suc->left) 
                    suc = suc->left; 
            } 
  
            // the maximum value in left subtree 
            // is successor. 
            if (root->left) { 
                pre = root->left; 
                while (pre->right) 
                    pre = pre->right; 
            } 
  
            return; 
        } 
  
        // If key is greater than root, then 
        // key lies in right subtree. Root 
        // could be predecessor if left 
        // subtree of key is null. 
        else if (root->key < key) { 
            pre = root; 
            root = root->right; 
        } 
  
        // If key is smaller than root, then 
        // key lies in left subtree. Root 
        // could be successor if right 
        // subtree of key is null. 
        else { 
            suc = root; 
            root = root->left; 
        } 
    } 
} 

Note: If you have any related doubts, queries, feel free to ask by commenting down below.

And if my answer suffice your requirements, then kindly upvote.

Happy Learning