jain12

delete a node in BST

Mar 12th, 2020
89
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.59 KB | None | 0 0
  1. #include<iostream>
  2. using namespace std;
  3. class Node{
  4.   public:
  5.       int data;
  6.       Node *left,*right;
  7.       Node(int key){
  8.         data=key;
  9.         left=right=NULL;
  10.         }
  11.   };
  12.  
  13.  void Inorder(Node *root){
  14.    if(root==NULL)
  15.      return;
  16.    Inorder(root->left);
  17.    cout<<" "<<root->data;
  18.    Inorder(root->right);
  19.    }
  20.  
  21. Node* InorderSuccessor(Node *node){
  22.  if(node->left==NULL)
  23.    return node;
  24.  else
  25.    return InorderSuccessor(node->left);
  26.   }
  27.  
  28.  Node* Delete(Node *root,int key){
  29.   if(root==NULL)
  30.     return root;
  31.   if(root->data<key)
  32.     root->right=Delete(root->right,key);
  33.   else
  34.     if(root->data>key)
  35.       root->left=Delete(root->left,key);
  36.     else{
  37.      Node *temp=root;
  38.       if(root->left==NULL){
  39.         root=root->right;
  40.         delete temp;
  41.         }
  42.      else
  43.        if(root->right==NULL){
  44.          root=root->left;
  45.          delete temp;
  46.         }
  47.        else{
  48.          Node *successor_node=InorderSuccessor(root->right);
  49.          root->data=successor_node->data;
  50.          root->right=Delete(root->right,successor_node->data);
  51.           }
  52.       }
  53.     return root;
  54.   }
  55.  
  56. void Insert(Node **root_ref,int key){
  57.   if(*root_ref==NULL){
  58.     *root_ref=new Node(key);
  59.     return;
  60.     }
  61.   if((*root_ref)->data<key)
  62.     Insert(&((*root_ref)->right),key);
  63.   else
  64.      if((*root_ref)->data>key)
  65.        Insert(&((*root_ref)->left),key);
  66.   }
  67.  
  68. int main(){
  69.  Node *root=NULL;
  70.  Insert(&root,5);
  71.   Insert(&root,7);
  72.  Insert(&root,6);
  73.  Insert(&root,2);
  74.  Insert(&root,8);
  75.  Inorder(root);
  76.  root=Delete(root,7);
  77.  cout<<" after deletion ";
  78.  Inorder(root);
  79.  }
Add Comment
Please, Sign In to add comment