Delete a node in Binary Search Tree

code:

#include<bits/stdc++.h>
using namespace std;

struct Node{
    int data;
    struct Node* left;
    struct Node* right;
};

Node* FindMin(Node* root)
{
    while(root->left!=NULL)
        root=root->left;
    return root;
}

//Function to search a delete value from tree
struct Node* Delete(struct Node *root, int data)
{

    if(root==NULL)
        return root;
    else if(data<root->data)
        root->left=Delete(root->left,data);
    else if(data>root->data)
        root->right=Delete(root->right,data);
    else{
        //case 1: No child
        if(root->left==NULL && root->right==NULL)
        {
            delete root;
            root=NULL;
        }
        //case 2: one child
        else if(root->left==NULL)
        {
            struct Node* temp=root;
            root=root->right;
            delete temp;
        }
        else if(root->right==NULL)
        {
            struct Node* temp=root;
            root=root->left;
            delete temp;
        }
        //case 3: 2 children
        else{
            struct Node * temp=FindMin(root->right);
            root->data=temp->data;
            root->right=Delete(root->right, temp->data);
        }

    }
return root;
}

//function to visit nodes in inorder
void Inorder(Node* root)
{
    if(root==NULL)
          return;
    Inorder(root->left); //visit left subtree
    printf("%d ",root->data); //print data
    Inorder(root->right); //visit right subtree
}


Node* Insert(Node *root, char data)
{
    if(root==NULL)
    {
        root=new Node();
        root->data=data;
        root->left=root->right=NULL;
    }
    else if(data<=root->data)
        root->left=Insert(root->left,data);
    else
        root->right=Insert(root->right,data);
    return root;
}

int main()
{
    Node *root=NULL;
    root=Insert(root,5);
    root=Insert(root,10);
    root=Insert(root,3);
    root=Insert(root,4);
    root=Insert(root,1);
    root=Insert(root,11);

    root=Delete(root,5);

    //Print Nodes in Inorder
    cout<<"Inorder: ";
    Inorder(root);
    cout<<"\n";

}

It would be a great help, if you support by sharing :)
Author: zakilive

Leave a Reply

Your email address will not be published.