Coders Packet

Basic Operation on Binary Search Tree (BST) using C++.

By Rahul Sah

In this article, we are going to learn Binary Search Tree and implementation of few operations on BST using C++ .

Binary Search Tree

A Binary Search Tree (BST) is a tree in which all the nodes follow certain properties like the value of the key of the left sub-tree is less than the value of its parent (root) node's key and the value of the key of the right sub-tree is greater than or equal to the value of its parent (root) node's key.

Implementation of a node using structures 

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

where struct node * left stores address of left subtree and struct node* right stores the address of right subtree.

Basic Operation on Binary Search Tree -

1.Insertion

2.Searching

3.Deletion

4.Inorder Traversal,Pre-Order Traversal , Post - Order Traversal 

Insertion

While inserting a value in BST is similar to searching because we try to maintain the rule that the left subtree is lesser than the root and the right subtree is larger than the root.

Generally, the time complexity for insertion of a node in BST is O(h) where h is the height of BST.

We are going to see code for the insertion of a node in the tree.

void insert() functions take the key to be inserted in the tree.

void insert(int x)
{
  struct node* temp;
  temp=(struct node*)malloc(sizeof(struct node));
  temp->data=x;
  temp->left=NULL;
  temp->right=NULL;
  if(root==NULL)
  {
    root=temp;
  }
  else
  {
    struct node* curr,*parent;
    curr=parent=root;
    while(curr)				//current variable is only for check where the entered data fits
    {
      parent=curr;		//parent variable points to that node
      if(temp->data > curr->data)
      {
        curr=curr->right;
      }
      else
      {
        curr=curr->left;
      }
    }
    if(temp->data > parent->data)
    {
      parent->right=temp;
    }
    else
    {
      parent->left=temp;
    }
    
  }
  
}

Searching

Whenever an element is to be searched, start searching from the root node and if the data is less than the (root->data) value, search for the element in the left subtree. Otherwise, search for the element in the right subtree. Follow the same algorithm for each node.

The time complexity for searching a node in BST is O(h) where h is the height of BST.

We are going to see code for searching a node in the tree.

int search() functions take the key to be searched in the tree returns 1 if the key is present in the tree and 0 if the element is not found.

int search(struct node *root, int value)
{
  struct node *temp = new node;
  temp = root;
  while(temp != NULL)
  {
    if(temp->data == value)
    {
      return 1;
    }
    else if(temp->data > value)
      temp = temp->left;
    else
      temp = temp->right;
  }
  return 0;
}

 

Deletion

Generally, the node to be deleted can a leaf node, the node having a single child, the node having two children. We will see one by one deletion of each type node.

In general, deletion in a binary tree has the worst-case complexity of O(n). In general, the time complexity is O(h).

A) Node to be deleted is the leaf: 

Deleting a leaf node is easy, traverse through the whole tree if the required node with the given data is found simply delete that node by placing NULL at the address of the current node.

 

B) Node to be deleted has only one child: 

We Simply copy the data of the successor node in the current node and remove the child of that node.

C) Node to be deleted has two children: 

Deleting a node having two children is quite challenging. Traverse through the tree and if the node to be deleted is found simply replace the value with minimum from the right subtree or maximum from the left subtree and remove the minimum or maximum value node.We have used finding minVlaue node from the right subtree.
 

              50                            60
           /     \         delete(50)      /   \
          40      70       --------->    40    70 
                 /  \                            \ 
                60   80                           80

 

We will see the implementation part below :
struct node* delete_node(struct node* root,int element)
{	
  
  if(root==NULL)
    return root;
  if(element > root->data)
  {
    root->right=delete_node(root->right,element);	
  }
  else if(element < root->data)
  {
    root->left=delete_node(root->left,element);
  }
  else{
    if(root->left==NULL)
    {
      struct node* y=root->right;
      //root->right=NULL;		//now both side of root has NULL so make it free
      free(root);
      return y;
    }
    else if(root->right==NULL)
    {
      struct node* y=root->left;
      //root->left=NULL;		//both side of root is NULL we can delete root completely
      free(root);
      return y;
    }
    else{
      struct node* y=minValueNode(root->right);
      root->data=y->data;
      root->right=delete_node(root->right,y->data);
    }
    
  }
  return root;
}

 

Inorder Traversal of BST 

Linear data structures (Array, Linked List, Queues, Stacks, etc) have only one logical way to traverse them, trees can be traversed in different ways like 1.Inorder Traversal 

2.Preorder Traversal

3.Postorder Traversal

 Implementation of inorder traversal of the tree, which generally prints the key in sorted order.

void inorderTraversal(struct node* root)
{
  if(root->left){
    inorderTraversal(root->left);
  }
  cout<data<<" ";
  if(root->right){
    inorderTraversal(root->right);
  }
}

In this way, we have performed basic operations in BST using C++ language. Keep exploring, I hope it was easy enough to understand. If you have any doubt, feel free to ask in the comment section. All the best! Keep learning.

Thank you!

Regards,
Rahul Sah
Codespeedy Tech Pvt. Ltd.

 

Download project

Reviews Report

Submitted by Rahul Sah (rahulsah1436)

Download packets of source code on Coders Packet