Operations on Binary Search Tree (BST)

1. Searching

In BST, Searching of the desired data item can be performed by branching into left or right subtree until the desired data item is found.

Algorithm

1. If the tree is empty or the element is the same as the element in the root, return the root.
2. If the element is less than the root element, search for the element in the left subtree of the given tree recursively.
3. If the element is greater than the root element, search for the element in the right subtree of the given tree recursively.

Pseudocode

search(root, element){
  if(root == NULL or element == root->element){
    return root
  }else if(element < root-> element){
    search(root->left, element)
  }else{
    search(root->right, element)
  }
}

2. Insertion

A new key is always inserted at the leaf by maintaining the property of the binary search tree. We start searching for a key from the root until we hit a leaf node. Once a leaf node is found, the new node is added as a child of the leaf node.

Algorithm

1. If the tree is empty, create a new node, store the data in it, and make this new node the root of the tree. Otherwise, compare the data to the data stored at the root.
2. If the data is identical to the root, do not change the tree.
3. If the data is smaller, insert the new item into the left subtree of the root recursively.
4. If the data is greater, insert the new item into the right subtree of the root recursively.

Pseudocode

Node * insert(Node *root, int data){

 if(root == NULL){
  root = new Node();
  root->data = data;
  root->left = NULL;
  root->right = NULL;
  return root;
 }
 if(data < root->data){
  root->left = insert(root->left, data);
 }else{
  root->right = insert(root->right, data);
 }

  return root;
}

3. Deletion

For Deletion we consider three cases:

Algorithm

1. Start at the root node of the BST.

2. Compare the value of the node to be deleted with the value of the root node.

3. If the value of the node to be deleted is less than the value of the root node, go to the left subtree of the root node recursively.

4. If the value of the node to be deleted is greater than the value of the root node, go to the right subtree of the root node recursively.

5. If the value of the node to be deleted is equal to the value of the root node, perform the deletion operation.

6. If the node to be deleted is a leaf node or has only one child, perform the deletion operation directly.

7. If the node to be deleted has two children, find the minimum value in the right subtree to replace it with and perform the deletion operation.

Pseudocode

node* delete_node(node *root, int data)
{
 if(root == nullptr) return root;
 else if(data < root->data) root->left = delete_node(root->left, data);
 else if(data > root->data) root->right = delete_node(root->right, data);
 else
 {
 if(root->left == nullptr && root->right == nullptr) // Case 1
 {
 free(root);
 root = nullptr;
 }
 else if(root->left == nullptr) // Case 2
 {
 node* temp = root;
 root= root->right;
 free(temp);
 }
 else if(root->right == nullptr) // Case 2
 {
 node* temp = root;
 root = root->left;
 free(temp);
 }
 else // Case 3
 {
 node* temp = root->right;
 while(temp->left != nullptr) temp = temp->left;
 root->data = temp->data;
 root->right = delete_node(root->right, temp->data);
 }
 }
 return root;
}

4. FindMin

The left subtree of a node contains nodes with keys smaller than the node's key, and the leftmost node has the minimum value. The leftmost node is a left node without a left child.

Algorithm

1. Traverse the node from root to left recursively until left is NULL.

2. The node whose left is NULL is the node with minimum value.

Pseudocode

int FindMin(struct node* node)  
{  
    struct node* current = node;  
    while (current->left != NULL)  
    {  
        current = current->left;  
    }  
    return(current->key);  
}  

5. FindMax

The right subtree of a node contains nodes with keys greater than the node's key, and the rightmost node has the maxValue value. The rightmost node is a right node without a right child.

Algorithm

1. Traverse the node from root to right recursively until right is NULL.

2. The node whose right is NULL is the node with maximum value.

Pseudocode

int FindMax(struct node* node)  
{  
    struct node* current = node;  
    while (current->right != NULL)  
    {  
        current = current->right;  
    }  
    return(current->key);  
}