Ticker

6/recent/ticker-posts

Header Ads Widget

Responsive Advertisement

Delete a node from BST


Node*inOrderSuccesor(Node*root)
{
    Node*curr=root;
    while(curr && curr->left!=NULL)
    {
        curr=curr->left;
    }
    return curr;
}
Node *deleteNode(Node *root, int X) {
     if(root==NULL)
    {
        return root;
    }
    if(root->data==X)
    {
        // for leaf node
       if(root->left==NULL && root->right==NULL)
       {
           delete root;
           return NULL;
       }
       // if one child,means no right child
       else if(root->right==NULL)
       {
           Node*temp=root->left;
           delete root;
           return temp;
           
       }
       // if one child , mans no left child
       else if(root->left==NULL)
       {
        Node*temp=root->right;
        delete root;
        return temp;
           
       }
       // when both child
       else
       {
         Node*temp=inOrderSuccesor(root->right);
         root->data=temp->data;
         root->right=deleteNode(root->right,temp->data);
       }
    }
    else if(root->data>X)
    {
       root->left= deleteNode(root->left,X);
    }
    else{
       root->right= deleteNode(root->right,X);
    }
}

Post a Comment

0 Comments