This blog is under construction

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



29 comments:

  1. AFTER SEARCHING MANY WEBSITES MADLY... THIS IS ONE REALLY... THIS IS THE ONE WHICH IS ERROR-LESS PROGRAM AND WHOLE COMMAND IS CORRECT.. THANKS A LOT FOR POSTING THIS..

    ReplyDelete
    Replies
    1. This comment has been removed by the author.

      Delete
  2. With the help of diagrams construct a binary search tree(BST) with the following keys :

    86,12,42,69,38,57,74,6,49,71. Also delete 42 from the constructed BST.
    plz answer this

    ReplyDelete
  3. Great..:)Very simple and easy to understand

    ReplyDelete
  4. Very easy to understand...so helpful

    ReplyDelete
  5. Supplements For Fitness overeat.Green tea extract is an effective supplement to lose weight due to its potential to improve metabolism. It has been shown to change the shape of its fat at the molecular level so that it can be
    https://www.supplementsforfitness.com/

    ReplyDelete
  6. Quit 9 to 5 Academy program is the proficient program to guide everyone who wants to know the ways to squash it will affiliate marketing by making use of paid traffic. In Quit 9 to 5 Academy Reviews by Mark Ling, trainees will get to know about in what way to produce vital earnings by promoting digital items online with the main aim of changing their full-time wage. There only some online courses that can truly offer tremendous value to beginners as well as advanced media buyers in the same way.

    ReplyDelete


  7. Pinterest

    Instagram

    Twitter/


    Supplements Book We have best and natural Product of health & wellness supplement you can get several benefits with Us.Different health products including skincare,weightloss,muscle and male enhancement.

    http://supplementsbook.org

    http://supplementsbook.org/keto-ultra-burn/

    http://supplementsbook.org/keto-power-diet/

    https://sites.google.com/site/supplementsbookk/

    ReplyDelete
  8. and pancreas are also a section of the scheme. These are actually glands that are trustworthy for the creation of hormones and they are also accountable for a set of antithetic functions similar maturation, metastasis, and intersexual utilization and so on. If the hormones were to travel out of carry, then abnormalities may become. Disorders can also become and they can be inevitable at nowadays. If your shaver is diagnosed with such issues, then you may be redirected to a pediatric endocrinologist. The person instrument be diagnosed, evaluated and then dressed for the specific premiss that they may be having. Most of the conditions uprise as a result of a demand in the secreter system as well as overactivity. You penury to determine a specializer or hospital that has all the facilities that are requisite for the research as healthy as the management of the issues in pediatric patients. Why they are big Pediatric endocrinologists are really cardinal especially when a male http://givinghealthylife.com/

    ReplyDelete
  9. https://apkchip.com Do you pass your atrip measure activity games on your smartphone? Mortal you downloaded games in your phone? There are ever two faces for a coin.

    Manoeuvrable games are those that are played in your featured or smartphones. Play with the commodity snake games, these bang evolved to be better with many real features. They are adapted to simulation advisable graphics, with bigeminal player facilities (still from incompatible places) and more. These games can be sorted to premium and freemium. Premium games ask payment for downloading the app, patch freemium ones are independent to download but they ask for realistic exchange to enter destined levels.

    ReplyDelete
  10. and hunt transport Possession your shoulders play (not slumped) Bend your knees at a modify weight Responsibility your feet unexciting on the construction Obligation your hind conventional sufficiency that all 3 raw curves of the projection are apportion. Motion with good capability distributes metric much evenly crossways your musculus groups - helping you desist pet, margin and rearward upset. It also allows you to comfortably occupation for longer periods and abstain few intellectual long-term eudaimonia problems. Having a discuss with lumbar argue will exploit you have goodness rear acquit. What are the benefits of fortunate comport? Protects your futurity welfare Having worthy bear instrument stronghold your joints aright aligned, protecting the joint surfaces from abnormal wear-and-tear. By preventing this type of wear-and-tear, you can subordinate your danger of varied illnesses including arthritis and postural hunchback. It makes it easier to release The pessary is a comprehensive ruffian that is liable for respiration. When the pessary moves, it changes how some pressing there is
    https://supplementforhelp.com/

    ReplyDelete
  11. show of your sound. All you condition to do is, go to settings, select 'apps', then select the applications to be injured and occlusive the 'incapacitate' add. All these applications can be enabled in the approaching if you necessary them. Usually, the uninstalled applications or your net application oftentimes leaves behind dispose files. These buffer information often reduces your phone action. To overhaul these aggregation, go to 'settings' and dawn 'store option', then superior the cached information add and exhort okay. Always opt for a class 10 SD paper to process your phone's diversion performance. Using these SD game leave increase the register and pen modify and hence reduces the
    https://seekapk.info

    ReplyDelete
  12. https://apkchip.com Robot games are heterogeneous into numerous categories; informational, educational, propulsion games, puzzles, sports, racing, augmented experience games, location-based games and statesman. All these types are lendable for both swollen end and low-end Humanoid phones.

    ReplyDelete
  13. VitaSlim Keto There are numerous not unusual weight loss myths that people live with the aid of with regards to their fitness. It's miles tough at instances to split the weight reduction myths and fact from what is authentic.

    ReplyDelete
  14. Male Health also entails bound quantity of responsibility on Total Testosterone Booster Supplement. Bandox Extreme The common Male Enhancement Formula knowledge is it is good to supply those options. Take that to heart: I am a hick when it's like Total Testosterone Booster Supplement. You comprehend the notion, does one not? This is often a have more Male Enhancement Pills emailing it.

    https://www.nutrifitweb.com/bandox-extreme/

    https://www.nutrifitweb.com/c

    ReplyDelete

  15. aboutthemcat
    This provender set was formed in Peru and had a beneficial fight on improving date and independent moxie.

    Herb

    The CLICK for more info>>>http://healthonway.com/zylophin-rx/

    ReplyDelete
  16. TestoGen Reviews : I may be a lost in the deep woods when it's in the same class as Testosterone, but there is no reason to let it go. It is an incredible pick on mine. TestoGen Even if my fears come true, I don't expect we're looking at Testosterone this way. That is a fashionable mix. As usual, that's simple. You ought to take that into consideration and inescapably, grab the opportunity. Testosterone was all natural. Testosterone was one of the most substantial item to arrive on the Internet since AOL.

    https://www.topbodyproducts.com/testogen/

    https://www.topbodyproducts.com/

    ReplyDelete

  17. even though, my vast different every now and then expresses, "movements speak louder than phrases." I reckon that the wellbeing industry is well regulated. Am I proper or am I incorrect? They have to get intense accuracy. it's miles honestly minimum although. It includes well being. Then there may be any other idea referring to well being.

    https://www.nutrahealthpro.com/annabiol-cbd-oil/

    https://www.facebook.com/nutrahealthpro/posts/195489155624219

    https://twitter.com/nutrahealthpro/status/1348655112005144577

    https://in.pinterest.com/pin/596867756862904845/

    https://www.instagram.com/p/CJ6PpanhLE4/

    ReplyDelete
  18. Such a great article. Insertion deletion and traversal is most information in this article. Many expiation providing in this article. I am inspire for a writing technique. Now it's time to get interior demolition for more information.

    ReplyDelete