What is binary search tree? Write a program to implement insertion and deletion algorithms in binary search tree.

Answers

This answer is not selected as best answer. This answer may not be sufficient for exam.

Your limit has been exceed. We have implemented this system because, We got difficulty on managing our servers. Please donate some amount to remove this limit.

Quota: 0 / 30

Donate

Binary Search Tree is a binary tree that is either empty or in which every node contains a key and satisfy the following conditions:

  1. All keys in the left sub-tree of the root are smaller than the key in the root node.
  2. All the keys in the right sub tree are greater than the key in the root node.
  3. The left and right sub-trees of the root are again binary search trees.

Example: BST tree of numbers: 50, 70, 60, 20, 90, 10, 40, 100

Binary Search Tree | HAMROCSIT

Program:

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

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


struct node *newNode(int item){
    struct node *temp = (struct node *)malloc(sizeof(struct node));
    temp->key = item;
    temp->left = temp->right = NULL;
    return temp;
}


void inorder(struct node *root){
    if (root != NULL){
        inorder(root->left);
        printf("%d -> ", root->key);
        inorder(root->right);
    }
}

struct node *insert(struct node *node, int key){
    if (node == NULL)
        return newNode(key);
    if (key < node->key)
        node->left = insert(node->left, key);
    else
        node->right = insert(node->right, key);
    return node;
}


struct node *minValueNode(struct node *node){
    struct node *current = node;
    while (current && current->left != NULL)
        current = current->left;
    return current;
}


struct node *deleteNode(struct node *root, int key){
    if (root == NULL)
        return root;

    if (key < root->key)
        root->left = deleteNode(root->left, key);
    else if (key > root->key)
        root->right = deleteNode(root->right, key);
    else{
        if (root->left == NULL){
            struct node *temp = root->right;
            free(root);
            return temp;
        }else if (root->right == NULL){
            struct node *temp = root->left;
            free(root);
            return temp;
        }

        struct node *temp = minValueNode(root->right);
        root->key = temp->key;
        root->right = deleteNode(root->right, temp->key);
    }
    return root;
}

int main(){
    struct node *root = NULL;
    root = insert(root, 6);
    root = insert(root, 7);
    root = insert(root, 3);
    root = insert(root, 2);
    root = insert(root, 4);
    root = insert(root, 19);
    root = insert(root, 17);
    root = insert(root, 8);

    printf("Inorder traversal:");
    inorder(root);

    printf("\nAfter deleting 10\n");
    root = deleteNode(root, 10);
    printf("Inorder traversal: ");
    inorder(root);
}

The output of above program is

Inorder traversal:2 -> 3 -> 4 -> 6 -> 7 -> 8 -> 17 -> 19 -> 
After deleting 10
Inorder traversal: 2 -> 3 -> 4 -> 6 -> 7 -> 8 -> 17 -> 19 ->
If you found any type of error on the answer then please mention on the comment or submit your new answer.
Leave your Answer:

Click here to submit your answer.

Discussion
0 Comments
  Loading . . .