Binary Search Tree (BST)

It is a data structure that quickly allows us to maintain a sorted list of numbers.

Also:

• It is called a binary tree because each tree node has max two children

• It is called search tree because it can be used to search for the presence of number in O(log(n)) time

Now you might wonder what differentiates it from the regular binary tree;

1. All nodes of left subtree are less than the root node

2. All nodes of the right subtree are more than the root node

3. Both subtrees of each node are also BST's which means they follow the above two properties.

There are three basic operations that you can perform on a binary search tree:

1. Search Operation

The algorithm depends on the property of BST that if each left subtree has values less than root and each right subtree has values greater than root.

• If the value is less than root we can say for sure that the value is not in the right subtree; now we need to only search in the left subtree and

• If the value is less than root we can say for sure that the value is not in the left subtree; now we need to only search in the right subtree.

Algorithm:

if root == NULL
	return NULL;
if number == root -> data
	return root -> data;
if number < root -> data
	return search( root->left );
if number > root -> data
	return search( root -> right ); 

---

2. Insertion Operation

A new key is always inserted at the leaf. Inserting a value in the correct position is similar to searching because we try to maintain the rule that the left subtree is lesser than root and right subtree is larger than root.

We keep going to either right subtree or left subtree depending on the value and when we reach a point left or right subtree is null, we put the new node there.

Algorithm:

if node == NULL
	return create_Node(data);
if (data < node -> data)
	node ->left = insert(node ->left, data);
else if (data > node ->data)
	node ->right = insert(node ->right, data);
return node;

---

3. Deletion Operation

There are three cases for deleting a node from a binary search tree.

Case I

In the first case, the node to be deleted is a leaf node so simply delete the node from the tree.

40 is to be deleted

Delete the node

Case II

In the second case, the node to be deleted has a single child node.

In such case:

1. Replace that node with its child node.

2. Remove the child node from its original position.

60 is to be deleted

Copy the value of its child to the node and delete the child

Final Tree

Case III

In this case, the node to be deleted has two children.

In such case:

1. Get the inorder successor of that node.

2. Replace the node with the inorder successor.

3. Remove the inorder successor from its original position.

30 is to be deleted

Copy the value of the inorder successor(40) to the node

Delete the inorder successor

Implementation using C:

#include <stdio.h>
#include <stdlib.h>

struct node {
  int key;
  struct node *left, *right;
};

// Create a node
struct node *newNode(int item) {
  struct node *temp = (struct node *)malloc(sizeof(struct node));
  temp->key = item;
  temp->left = temp->right = NULL;
  return temp;
}

// Inorder Traversal
void inorder(struct node *root) {
  if (root != NULL) {
    // Traverse left
    inorder(root->left);

    // Traverse root
    printf("%d -> ", root->key);

    // Traverse right
    inorder(root->right);
  }
}

// Insert a node
struct node *insert(struct node *node, int key) {
  // Return a new node if the tree is empty
  if (node == NULL) return newNode(key);

  // Traverse to the right place and insert the node
  if (key < node->key)
    node->left = insert(node->left, key);
  else
    node->right = insert(node->right, key);

  return node;
}

// Find the inorder successor
struct node *minValueNode(struct node *node) {
  struct node *current = node;

  // Find the leftmost leaf
  while (current && current->left != NULL)
    current = current->left;

  return current;
}

// Deleting a node
struct node *deleteNode(struct node *root, int key) {
  // Return if the tree is empty
  if (root == NULL) return root;

  // Find the node to be deleted
  if (key < root->key)
    root->left = deleteNode(root->left, key);
  else if (key > root->key)
    root->right = deleteNode(root->right, key);

  else {
    // If the node is 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;
    }

    // If the node has two children
    struct node *temp = minValueNode(root->right);

    // Place the inorder successor in position of the node to be deleted
    root->key = temp->key;

    // Delete the inorder successor
    root->right = deleteNode(root->right, temp->key);
  }
  return root;
}

// Driver code
int main() {
  struct node *root = NULL;
  root = insert(root, 80);
  root = insert(root, 30);
  root = insert(root, 10);
  root = insert(root, 60);
  root = insert(root, 70);
  root = insert(root, 100);
  root = insert(root, 140);
  root = insert(root, 40);

  printf("Inorder traversal: ");
  inorder(root);

  printf("\nAfter deleting 10\n");
  root = deleteNode(root, 10);
  printf("Inorder traversal: ");
  inorder(root);
}

Output:
Inorder traversal: 1 -> 3 -> 4 -> 6 -> 7 -> 8 -> 10 -> 14 -> 
After deleting 10
Inorder traversal: 1 -> 3 -> 4 -> 6 -> 7 -> 8 -> 14 -> 

---

Happy Coding!

Follow us on Instagram @programmersdoor

Join us on Telegram @programmersdoor

Please write comments if you find any bug in the above code/algorithm, or find other ways to solve the same problem.

Follow Programmers Door for more.

#blog #interview #placement #learn #computer #science