Tuesday, 5 March 2013

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
                                                         

See Also:
C Program To Represent Binary Search Tree Using Arrays
C Program To Perform Insertion, Deletion and Traversal In Binary Search Tree
C Program To Implement Binary Tree Traversals: In-order, Pre-order and Post-order
C Program To Implement Dictionary Using Binary Search Tree
C Program To Perform Searching in Binary Search Tree
C Program To Perform Insertion, Deletion And Traversal In Red Black Tree
C Program To Perform Insertion, Deletion and Traversal in AVL Tree
C Program To Perform Insertion, Deletion and Traversal In B-Tree
C Program To Implement Priority Queue Using Binary Heaps
Construct Binary Search Tree From In-order and Pre-order Traversal Outputs


Example Program For Insertion, Deletion And Traversal In Binary Search Tree:



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

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

  struct treeNode *root = NULL;

  /* create a new node with the given data */
  struct treeNode* createNode(int data) {
        struct treeNode *newNode;
        newNode = (struct treeNode *) malloc(sizeof (struct treeNode));
        newNode->data = data;
        newNode->left = NULL;
        newNode->right = NULL;
        return(newNode);
  }

  /* insertion in binary search tree */
  void insertion(struct treeNode **node, int data) {
        if (*node == NULL) {
                *node = createNode(data);
        } else if (data < (*node)->data) {
                insertion(&(*node)->left, data);
        } else if (data > (*node)->data) {
                insertion(&(*node)->right, data);
        }
  }


  /* deletion in binary search tree */
  void deletion(struct treeNode **node, struct treeNode **parent, int data) {
        struct treeNode *tmpNode, *tmpParent;
        if (*node == NULL)
                return;
        if ((*node)->data == data) {
                /* deleting the leaf node */
                if (!(*node)->left && !(*node)->right) {
                        if (parent) {
                                /* delete leaf node */
                                if ((*parent)->left == *node)
                                        (*parent)->left = NULL;
                                else
                                        (*parent)->right = NULL;
                                free(*node);
                        } else {
                                /* delete root node with no children */
                                free(*node);
                        }
                /* deleting node with one child */
                } else if (!(*node)->right && (*node)->left) {
                        /* deleting node with left child alone */
                        tmpNode = *node;
                        (*parent)->right = (*node)->left;
                        free(tmpNode);
                        *node = (*parent)->right;
                } else if ((*node)->right && !(*node)->left) {
                        /* deleting node with right child alone */
                        tmpNode = *node;
                        (*parent)->left = (*node)->right;
                        free(tmpNode);
                        (*node) = (*parent)->left;
                } else if (!(*node)->right->left) {
                        /*
                         * deleting a node whose right child
                         * is the smallest node in the right
                         * subtree for the node to be deleted.
                         */

                        tmpNode = *node;

                        (*node)->right->left = (*node)->left;

                        (*parent)->left = (*node)->right;
                        free(tmpNode);
                        *node = (*parent)->left;
                } else {
                        /*
                         * Deleting a node with two children.
                         * First, find the smallest node in
                         * the right subtree.  Replace the 
                         * smallest node with the node to be
                         * deleted. Then, do proper connections
                         * for the children of replaced node.
                         */
                        tmpNode = (*node)->right;
                        while (tmpNode->left) {
                                tmpParent = tmpNode;
                                tmpNode = tmpNode->left;
                        }
                        tmpParent->left = tmpNode->right;
                        tmpNode->left = (*node)->left;
                        tmpNode->right =(*node)->right;
                        free(*node);
                        *node = tmpNode;
                }
        } else if (data < (*node)->data) {
                /* traverse towards left subtree */
                deletion(&(*node)->left, node, data);
        } else if (data > (*node)->data) {
                /* traversing towards right subtree */
                deletion(&(*node)->right, node, data);
        }
  }

  /* search the given element in binary search tree */
  void findElement(struct treeNode *node, int data) {
        if (!node)
                return;
        else if (data < node->data) {
                findElement(node->left, data);
        } else if (data > node->data) {
                findElement(node->right, data);
        } else
                printf("data found: %d\n", node->data);
        return;

  }

  void traverse(struct treeNode *node) {
        if (node != NULL) {
                traverse(node->left);
                printf("%3d", node->data);
                traverse(node->right);
        }
        return;
  }

  int main() {
        int data, ch;
        while (1) {
                printf("1. Insertion in Binary Search Tree\n");
                printf("2. Deletion in Binary Search Tree\n");
                printf("3. Search Element in Binary Search Tree\n");
                printf("4. Inorder traversal\n5. Exit\n");
                printf("Enter your choice:");
                scanf("%d", &ch);
                switch (ch) {
                        case 1:
                                while (1) {
                                printf("Enter your data:");
                                scanf("%d", &data);
                                insertion(&root, data);
                                printf("Continue Insertion(0/1):");
                                scanf("%d", &ch);
                                if (!ch)
                                        break;
                                }
                                break;
                        case 2:
                                printf("Enter your data:");
                                scanf("%d", &data);
                                deletion(&root, NULL, data);
                                break;
                        case 3:
                                printf("Enter value for data:");
                                scanf("%d", &data);
                                findElement(root, data);
                                break;
                        case 4:
                                printf("Inorder Traversal:\n");
                                traverse(root);
                                printf("\n");
                                break;
                        case 5:
                                exit(0);
                        default:
                                printf("u've entered wrong option\n");
                                break;
                }
        }
        return 0;

  }



Note: Data in yellow color are comments.
  Output: (C Program For Insertion, Deletion & Traversal In BST Tree)
  jp@jp-VirtualBox:$ ./a.out
  1. Insertion in Binary Search Tree
  2. Deletion in Binary Search Tree
  3. Search Element in Binary Search Tree
  4. Inorder traversal
  5. Exit
  Enter your choice:1
  Enter your data:20
  Continue Insertion(0/1):1
  Enter your data:14
  Continue Insertion(0/1):1
  Enter your data:9
  Continue Insertion(0/1):1
  Enter your data:19
  Continue Insertion(0/1):1
  Enter your data:25
  Continue Insertion(0/1):1
  Enter your data:21
  Continue Insertion(0/1):1
  Enter your data:23
  Continue Insertion(0/1):1
  Enter your data:30
  Continue Insertion(0/1):1
  Enter your data:26
  Continue Insertion(0/1):0    
  Resultant Binary Search Tree after insertion operation:
                                                    20
                                                 /      \
                                              14        25
                                             /    \      /   \
                                           9      19  21   30
                                                         \      /
                                                        23   26 
    
  1. Insertion in Binary Search Tree
  2. Deletion in Binary Search Tree
  3. Search Element in Binary Search Tree
  4. Inorder traversal
  5. Exit
  Enter your choice:4
  Inorder Traversal:
  9 14 19 20 21 23 25 26 30
  1. Insertion in Binary Search Tree
  2. Deletion in Binary Search Tree
  3. Search Element in Binary Search Tree
  4. Inorder traversal
  5. Exit
  Enter your choice:2
  Enter your data:9

  Delete node 9
                                                    20
                                                 /      \
                                              14        25
                                                  \      /   \
                                                  19  21   30
                                                         \      /
                                                        23   26

  1. Insertion in Binary Search Tree
  2. Deletion in Binary Search Tree
  3. Search Element in Binary Search Tree
  4. Inorder traversal
  5. Exit
  Enter your choice:4
  Inorder Traversal:
  14 19 20 21 23 25 26 30
  1. Insertion in Binary Search Tree
  2. Deletion in Binary Search Tree
  3. Search Element in Binary Search Tree
  4. Inorder traversal
  5. Exit
  Enter your choice:2
  Enter your data:14

  Delete node 14
                                                    20
                                                 /      \
                                              19        25
                                                         /   \
                                                        21   30
                                                         \      /
                                                        23   26

  1. Insertion in Binary Search Tree
  2. Deletion in Binary Search Tree
  3. Search Element in Binary Search Tree
  4. Inorder traversal
  5. Exit
  Enter your choice:4
  Inorder Traversal:
  19 20 21 23 25 26 30
  1. Insertion in Binary Search Tree
  2. Deletion in Binary Search Tree
  3. Search Element in Binary Search Tree
  4. Inorder traversal
  5. Exit
  Enter your choice:2
  Enter your data:30

  Delete node 30
                                                    20
                                                 /      \
                                              19        25
                                                         /   \
                                                        21   26
                                                         \      
                                                         23   

  1. Insertion in Binary Search Tree
  2. Deletion in Binary Search Tree
  3. Search Element in Binary Search Tree
  4. Inorder traversal
  5. Exit
  Enter your choice:4
  Inorder Traversal:
  19 20 21 23 25 26
  1. Insertion in Binary Search Tree
  2. Deletion in Binary Search Tree
  3. Search Element in Binary Search Tree
  4. Inorder traversal
  5. Exit
  Enter your choice:2
  Enter your data:20

  Delete node 20
                                                    21
                                                 /      \
                                              19        25
                                                         /   \
                                                        23   26
                                                             
                                                            

  1. Insertion in Binary Search Tree
  2. Deletion in Binary Search Tree
  3. Search Element in Binary Search Tree
  4. Inorder traversal
  5. Exit
  Enter your choice:4
  Inorder Traversal:
  19 21 23 25 26
  1. Insertion in Binary Search Tree
  2. Deletion in Binary Search Tree
  3. Search Element in Binary Search Tree
  4. Inorder traversal
  5. Exit
  Enter your choice:1
  Enter your data:15
  Continue Insertion(0/1):1
  Enter your data:14
  Continue Insertion(0/1):1
  Enter your data:16
  Continue Insertion(0/1):1
  Enter your data:17
  Continue Insertion(0/1):0
  Binary Search Tree After Insertion Operation:

                                                    21
                                                 /      \
                                              19        25
                                             /            /   \
                                           15         23   26
                                          /   \
                                        14   16
                                                 \ 
                                                 17 

  1. Insertion in Binary Search Tree
  2. Deletion in Binary Search Tree
  3. Search Element in Binary Search Tree
  4. Inorder traversal
  5. Exit
  Enter your choice:4
  Inorder Traversal:
  14 15 16 17 19 21 23 25 26
  1. Insertion in Binary Search Tree
  2. Deletion in Binary Search Tree
  3. Search Element in Binary Search Tree
  4. Inorder traversal
  5. Exit
  Enter your choice:2
  Enter your data:15
  Delete Node 15

                                                    21
                                                 /      \
                                              19        25
                                             /            /   \
                                           16         23   26
                                          /   \
                                        14   17

  1. Insertion in Binary Search Tree
  2. Deletion in Binary Search Tree
  3. Search Element in Binary Search Tree
  4. Inorder traversal
  5. Exit
  Enter your choice:4
  Inorder Traversal:
  14 16 17 19 21 23 25 26
  1. Insertion in Binary Search Tree
  2. Deletion in Binary Search Tree
  3. Search Element in Binary Search Tree
  4. Inorder traversal
  5. Exit
  Enter your choice:3
  Enter value for data:21
  data found: 21
  1. Insertion in Binary Search Tree
  2. Deletion in Binary Search Tree
  3. Search Element in Binary Search Tree
  4. Inorder traversal
  5. Exit
  Enter your choice:5



1 comment: