Binary Search Tree Data Structure

As we discussed in the previous article, the binary search tree is one of the types of trees with some specific properties. A binary search tree is quick, efficient, and easy to implement. In this article, we will learn the working of a binary search tree, its properties, and its implementation.

Binary search tree

BST, short for Binary search tree is a binary tree with specific following properties.

1. The nodes in the left subtree must be less than the root node
2. The nodes in the right subtree must be greater than the root node.
3. The left and the right subtrees must also be binary trees.

The above properties apply to each node of the binary tree for it to be a BST.

Operations on Binary Search Tree in data Structure

1. Searching in BST

Finding the location of an element in the BST

Algorithm

search(root)
If root == NULL 
    return NULL;
If Value == root->data 
    return root->data;
If Value < root->data 
    return search(root->left)
If Value > root->data 
    return search(root->right)

2. Inserting element in BST

Inserting a new element in the BST

Algorithm

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

3. Deleting element from BST

deleting an existing element from BST

Case 1: if a node is to be deleted from the Leaf node.

• Simply Delete the node from the leaf node.

Case 2: if the node that has to be deleted has 1 child

• Replace node with the child node
• Remove child node from the original position

Case 3: if the node that has to be deleted has 2 child

• Retrieve inorder successor of the node.
• Replace node with the inorder successor
• Remove inorder successor from its original position.

Working of Binary Search Tree

Let us take an example to demonstrate the working of BST with insert and delete operations

Step 1: insert 50

Step 2: insert 75

Step 3: insert 90

Step 4: insert 25

Step 5: insert 40

Step 6: insert 62

Step 7: insert 70

Step 8: delete 90. This is case 1 deletion.

Step 9: insert 92

Step 10: delete 25. This is case 2 deletion.

Step 11: delete 75. This is case 3 deletion.

Step 12: insert 30

Implementation of Binary Search Tree in C

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

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

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

void inorderTraversal(struct node *root) 
{
  if (root != NULL) 
  {
    inorderTraversal(root->left);

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

    inorderTraversal(root->right);
  }
}

struct node *insertNew(struct node *node, int Value)
{
  if (node == NULL) return newNode(Value);

  if (Value< node->key)
    node->left = insertNew(node->left, Value);
  else
    node->right = insertNew(node->right, Value);

  return node;
}

struct node *minValueNode(struct node *node) 
{
  struct node *current = node;

  while (current && current->left != NULL)
    current = current->left;

  return current;
}

struct node *deleteNode(struct node *root, int Value) 
{
  if (root == NULL) return root;

  if (Value < root->key)
    root->left = deleteNode(root->left, Value);
  else if (Value > root->key)
    root->right = deleteNode(root->right, Value);

  else 
  {
    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;
    }

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

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

int main() {
  struct node *root = NULL;
  root = insertNew(root, 8);
  root = insertNew(root, 3);
  root = insertNew(root, 1);
  root = insertNew(root, 6);
  root = insertNew(root, 7);
  root = insertNew(root, 10);
  root = insertNew(root, 14);
  root = insertNew(root, 4);

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

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

Binary Search Tree Implementation in C++

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
using namespace std;

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

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

void inorderTraversal(struct node *root) 
{
  if (root != NULL) 
  {
    inorderTraversal(root->left);

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

    inorderTraversal(root->right);
  }
}

struct node *insertNew(struct node *node, int Value)
{
  if (node == NULL) return newNode(Value);

  if (Value< node->key)
    node->left = insertNew(node->left, Value);
  else
    node->right = insertNew(node->right, Value);

  return node;
}

struct node *minValueNode(struct node *node) 
{
  struct node *current = node;

  while (current && current->left != NULL)
    current = current->left;

  return current;
}

struct node *deleteNode(struct node *root, int Value) 
{
  if (root == NULL) return root;

  if (Value < root->key)
    root->left = deleteNode(root->left, Value);
  else if (Value > root->key)
    root->right = deleteNode(root->right, Value);

  else 
  {
    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;
    }

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

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

int main() {
  struct node *root = NULL;
  root = insertNew(root, 8);
  root = insertNew(root, 3);
  root = insertNew(root, 1);
  root = insertNew(root, 6);
  root = insertNew(root, 7);
  root = insertNew(root, 10);
  root = insertNew(root, 14);
  root = insertNew(root, 4);

  cout << "Inorder traversal: ";
  inorderTraversal(root);

  cout << "\nAfter deleting 10\n";
  root = deleteNode(root, 10);
  cout << "Inorder traversal: ";
  inorderTraversal(root);
}

BST Implementation in JAVA

public class BinarySearchTree 
{
  class Node 
  {
    int key;
    Node left, right;

    public Node(int item)
    {
      key = item;
      left = right = null;
    }
  }

  Node root;

  BinarySearchTree()
  {
    root = null;
  }

  void insert(int key)
  {
    root = insertKey(root, key);
  }

  Node insertKey(Node root, int key) 
  {
    if (root == null) {
      root = new Node(key);
      return root;
    }

    if (key < root.key)
      root.left = insertKey(root.left, key);
    else if (key > root.key)
      root.right = insertKey(root.right, key);

    return root;
  }

  void inorder() 
  {
    inorderRec(root);
  }

  void inorderRec(Node root) 
  {
    if (root != null) 
    {
      inorderRec(root.left);
      System.out.print(root.key + " -> ");
      inorderRec(root.right);
    }
  }

  void deleteKey(int key)
  {
    root = deleteRec(root, key);
  }

  Node deleteRec(Node root, int key) 
  {
    if (root == null)
      return root;

    if (key < root.key)
      root.left = deleteRec(root.left, key);
    else if (key > root.key)
      root.right = deleteRec(root.right, key);
    else 
    {
      if (root.left == null)
        return root.right;
      else if (root.right == null)
        return root.left;
        
      root.key = minValue(root.right);

      root.right = deleteRec(root.right, root.key);
    }

    return root;
  }

  int minValue(Node root) 
  {
    int minv = root.key;
    while (root.left != null) 
    {
      minv = root.left.key;
      root = root.left;
    }
    return minv;
  }

  public static void main(String[] args) 
  {
    BinarySearchTree tree = new BinarySearchTree();

    tree.insert(8);
    tree.insert(3);
    tree.insert(1);
    tree.insert(6);
    tree.insert(7);
    tree.insert(10);
    tree.insert(14);
    tree.insert(4);

    System.out.print("Inorder traversal: ");
    tree.inorder();

    System.out.println("\n\nAfter deleting 10");
    tree.deleteKey(10);
    System.out.print("Inorder traversal: ");
    tree.inorder();
  }
}

Binary Search Tree Implementation in Python

class Node:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None

def inorderTraversal(root):
    if root is not None:
        inorderTraversal(root.left)
        print(str(root.key) + "->", end=' ')
        inorderTraversal(root.right)

def insertnew(node, value):

    if node is None:
        return Node(value)
    if value< node.key:
        node.left = insertnew(node.left, value)
    else:
        node.right = insertnew(node.right, value)

    return node

def minValueNode(node):
    current = node

    while(current.left is not None):
        current = current.left

    return current

def deleteNode(root, value):

    if root is None:
        return root
    if value < root.key:
        root.left = deleteNode(root.left, value)
    elif(value> root.key):
        root.right = deleteNode(root.right, value)
    else:
        if root.left is None:
            temp = root.right
            root = None
            return temp

        elif root.right is None:
            temp = root.left
            root = None
            return temp

        temp = minValueNode(root.right)

        root.key = temp.key
        root.right = deleteNode(root.right, temp.key)

    return root


root = None
root = insertnew(root, 8)
root = insertnew(root, 3)
root = insertnew(root, 1)
root = insertnew(root, 6)
root = insertnew(root, 7)
root = insertnew(root, 10)
root = insertnew(root, 14)
root = insertnew(root, 4)

print("Inorder traversal: ", end=' ')
inorderTraversal(root)

print("\nDelete 10")
root = deleteNode(root, 10)
print("Inorder traversal: ", end=' ')
inorderTraversal(root)

Advantages of Binary Search Tree

1. Searching is very easy in BST. At each step, we get to know which subtree might contain the element.
2. Insertion and deletion in BST is faster than arrays or linked lists
3. BST is very efficient in terms of complexity.

Complexity of Binary Search Tree

Space complexity for all operations in BST in O(n)

Applications of BST

1. It is implemented for dynamic sorting
2. It manages virtual memory area in UNIX kernel
3. It’s useful for multilevel indexing in database

Conclusion

BST is a fast and efficient algorithm with many real-world applications and advantages. We learned working and implementation of BST in different programming languages. In future articles, we will learn about AVL trees and, B-Tree, etc.