Insertion, Deletion And Traversal In Binary Search Tree

Insertion, Deletion And Traversal In Binary Search Tree

Insertion in Binary Search Tree:

• Check whether root node is present or not(tree available or not).  If root is NULL, create root node.
• If the element to be inserted is less than the element present in the root node, traverse the left sub-tree recursively until we reach T->left/T->right is NULL and place the new node at T->left(key in new node < key in T)/T->right (key in new node > key in T).
• If the element to be inserted is greater than the element present in root node, traverse the right sub-tree recursively until we reach T->left/T->right is NULL and place the new node at T->left/T->right.

Algorithm for insertion in Binary Search Tree:
TreeNode insert(int data, TreeNode T) {
          if T is NULL {
                  T = (TreeNode *)malloc(sizeof (Struct TreeNode));
                  (Allocate Memory of new node and load the data into it)
                  T->data = data;
                  T->left   = NULL;
                  T->right = NULL;
          } else if T is less than T->left {
                  T->left = insert(data, T->left);
                  (Then node needs to be inserted in left sub-tree.So, 
                    recursively traverse left sub-tree to find the place 
                    where the new node needs to be inserted)
          } else if T is greater than T->right {
                   T->right = insert(data, T->right);
                   (Then node needs to be inserted in right sub-tree
                    So, recursively traverse right sub-tree to find the 
                     place where the new node needs to be inserted.)
         }
         return T;
}

Example:
Insert 20 into the Binary Search Tree.  
Tree is not available.  So, create root node and place 10 into it.

                                                   20

Insert 23 into the given Binary Search Tree. 23 > 20 (data in root).  So, 23 needs to be inserted in the right sub-tree of 20.

                                                    20
                                                        \
                                                         23

Insert 13 into the given Binary Search Tree.  13 < 20(data in root).  So, 13 needs to be inserted in left sub-tree of 20.

                                                   20
                                                 /     \
                                              13       23

Insert 9 into the given Binary Search Tree.

                                                   20
                                                 /     \
                                              13       23
                                             /
                                           9 

Inserting 14.

                                                   20
                                                 /     \
                                              13       23
                                             /    \   
                                           9      14

Inserting 19.
                                                   20
                                                 /     \
                                              13       23
                                             /    \   
                                           9      14
                                                     \
                                                      19
Inserting 21.

                                                    20
                                                 /      \
                                              13        23
                                             /    \      / 
                                           9      14  21  
                                                     \
                                                      19
Inserting 27.
                                                    20
                                                 /      \
                                              13        23
                                             /    \      /  \
                                           9      14  21  27
                                                     \
                                                      19
Inserting 24.
                                                    20
                                                 /      \
                                              13        23
                                             /    \      /  \
                                           9      14  21  27
                                                     \       /
                                                      19  24


Deletion in Binary Search Tree:
How to delete a node from binary search tree?
There are three different cases that needs to be considered for deleting a node from binary search tree.

case 1: Node with no children (or) leaf node
case 2: Node with one child
case 3: Node with two children.

                                                    20
                                                 /      \
                                              13        23
                                             /    \      /  \
                                           9      14  21  27
                                                     \       /
                                                      19  24

Case 1: Delete a leaf node/ node with no children.

                                                    20
                                                 /      \
                                              13        23
                                             /    \      /  \
                                           9      14  21  27
                                                     \       /
                                                      19  24

Delete 24 from the above binary search tree.

                                                    20
                                                 /      \
                                              13        23
                                             /    \      /  \
                                           9      14  21  27
                                                     \      
                                                      19

Case 2: Delete a node with one child.

                                                    20
                                                 /      \
                                              13        23
                                             /    \      /  \
                                           9      14  21  27
                                                     \       /
                                                      19  24

Delete 14 from above binary search tree.

                                                    20
                                                 /      \
                                              13        23
                                             /    \      /  \
                                           9      19  21  27
                                                             /
                                                           24

Case 3: Delete a node with two children.
Delete a node whose right child is the smallest node in the right sub-tree. (14 is the smallest node present in the right sub-tree of 13).
                                                    20
                                                 /      \
                                              13        23
                                             /    \      /  \
                                           9      14  21  27
                                                     \       /
                                                      19  24

Delete 13 from the above binary tree.  Find the smallest in the left subtree of 13.  So, replace 13 with 14.

                                                    20
                                                 /      \
                                              14        23
                                             /   \       /  \
                                           9      19  21  27
                                                             /
                                                          24

Delete 20 from the below binary search tree.
                                                    20
                                                 /      \
                                              13        23
                                             /    \      /  \
                                           9      14  21  27
                                                          \
                                                          22

Find the smallest node in the right sub-tree of 20.  And that smallest node is 21.  So, replace 20 with 21.  Since 21 has only one child(22), the pointer currently pointing to 21 is made to point to 22.  So, the resultant binary tree would be the below.

                                                    21
                                                 /      \
                                              13        23
                                             /    \     /  \
                                           9      14       27
                                                          \
                                                          22


                                                    21
                                                 /      \
                                              13        23
                                             /    \     /   \
                                           9      14  22   27