Binary Search Tree

A Binary Search Tree is a binary tree data structure with the following properties :

- All the nodes in the left subtree of a node n have keys less than the key of node n
- All the nodes in the right subtree of a node n have keys greater than the key of node n
- There are no duplicate keys
- Both left and right subtrees must themselves be binary search trees

Example of BST ->

These properties make it easier for up to speed up operations such as search, insertion and deletion.

We can use a recursive function to search the left subtree if the target is smaller than the key of the node, if greater search the right subtree and if equal return the position of the node we're at.

Insertion is always done at leaf node. Example : 

 #include <iostream>  
 using namespace std;  
 // Implementation of Binary Tree Insertion in C++  
 struct tree{  
      int data;  
      struct tree * left;  
      struct tree * right;  
 };  
 struct tree * NewNode(int val)  
 {  
      struct tree * node = (struct tree *)malloc(sizeof(struct tree));  
      // struct tree * node;  
      //struct tree NewNode;  
      //node = &NewNode;  
      node->data = val;  
      node->left = node->right = NULL;  
      return node;  
 }  
 struct tree * insertNode(struct tree * t, int val)  
 {  
      if(t == NULL) { return NewNode(val); }  
      if(t->data > val){ t->left = insertNode(t->left, val); }  
      else { t->right = insertNode(t->right, val); }  
      return t;  
 }  
 int main()  
 {            
      struct tree * root = NULL;   
      root = insertNode(root,10);  
      insertNode(root,20);  
      insertNode(root,30);  
      insertNode(root,40);  
      insertNode(root,5);  
      /* The generated tree will be of the structure :  
                       10  
                       / \  
                      5  20  
                          \  
                          30  
                           \  
                           40  
      */  
 }  

The complexity of search, insertion and deletion in a binary search tree is O(h), where h is the height of the tree.

Deletion in a BST can be subdivided into three cases: 

when node to be deleted is,

1. Leaf Node - simply remove

2. Node with 1 child - Copy child to node and delete child

3. Node with 2 children - Copy contents of the inorder successor(in right subtree) to the node and delete the inorder successor.

Delete example : 

 #include <iostream>  
 using namespace std;  
 // Implementation of Binary Tree in C++  
 struct tree{  
      int data;  
      struct tree * left;  
      struct tree * right;  
 };  
 struct tree * NewNode(int val)  
 {  
      struct tree * node = (struct tree *)malloc(sizeof(struct tree));  
      // struct tree * node;  
      //struct tree NewNode;  
      //node = &NewNode;  
      node->data = val;  
      node->left = node->right = NULL;  
      return node;  
 }  
 struct tree * insertNode(struct tree * t, int val)  
 {  
      if(t == NULL) { return NewNode(val); }  
      if(t->data > val){ t->left = insertNode(t->left, val); }  
      else { t->right = insertNode(t->right, val); }  
      return t;  
 }  
 struct tree * inorderSuccessor(struct tree* t)  
 {  
   struct tree * current = t;  
   while (current->left != NULL) { current = current->left; }  
   return current;  
 }  
 struct tree * Delete(struct tree * t, int target)  
 {  
      if (t == NULL) { return t; }  
      if (t->data > target)   
      { t->left = Delete(t->left, target); }  
      else if (t->data < target)  
      { t->right = Delete(t->right, target); }  
      else  
      {       
           if(t->left == t->right && t->right == NULL) // This block can be avoided as the next block takes care of this case.  
           {  
                struct tree * temp;  
                temp = NULL;  
                free(t);  
                return temp;  
           }  
           else if(t->left == NULL)  
           {  
                struct tree * temp = t->right;  
                free(t);  
                return temp;  
           }  
           else if (t->right == NULL)  
           {  
                struct tree * temp = t->left;  
                free(t);  
                return temp;  
           }  
           else  
           {  
                // This is when t has two children  
                struct tree * temp = inorderSuccessor(t->right);  
                t->data = temp->data;  
                t->right = Delete(t->right, temp->data); // This is to delete inorder successor in right subtree  
           }  
      }   
      return t;  
 }  
 int main()  
 {            
      struct tree * root = NULL;   
      root = insertNode(root,10);  
      insertNode(root,20);  
      insertNode(root,30);  
      insertNode(root,40);  
      insertNode(root,5);  
      insertNode(root,15);  
      /* The generated tree will be of the structure :  
                          10  
                         /  \  
                        5    20  
                            /  \  
                           15  30  
                                 \  
                                 40  
      */  
      Delete(root,5);  
      /* The generated tree will be of the structure :  
                          10  
                            \  
                             20  
                            /  \  
                           15  30  
                                 \  
                                 40  
      */  
      Delete(root,20);  
      /* The generated tree will be of the structure :  
                          10  
                            \  
                             30  
                            /  \  
                           15   40  
      */  
      return 1;  
 }  

The inorder traversal of a BST gives us the sorted tree.