Skip to main content

Delete a node in binary search tree

Delete a node in binary search tree

Here given code implementation process.

//C Program 
//Delete a node in binary search tree
#include<stdio.h>
#include<stdlib.h>
//structure of Binary Search Tree node
struct Node
{
  int data;
  struct Node *left,*right; 
};

//Adding a new node in binary search tree
void add( struct Node **root, int data)
{
  //Create a dynamic node of binary search tree 
  struct Node *new_node = (struct Node *)malloc(sizeof(struct Node ));

  if(new_node!=NULL)
  {
    //Set data and pointer values
    new_node->data = data;
    new_node->left = NULL; //Initially node left-pointer is NULL
    new_node->right = NULL;//Initially node right-pointer is NULL

    if(*root == NULL)
    {
      //When adds a first node in binary tree
      *root = new_node;
    }
    else
    {
      struct Node *find = *root;

      //iterate binary tree and add new node to proper position
      
      while(find != NULL)
      {
        if(find -> data >= data)
        { 
          if(find->left==NULL)
          {
            find->left = new_node;
            break;
          }
          else
          { //visit left sub-tree
            find = find->left;
          }
        }
        else
        {
          if(find->right == NULL)
          {
            find->right = new_node;
            break;
          }
          else
          {
            //visit right sub-tree
            find = find->right;
          }
        }
      }
    }
  }else
  {
    printf("Memory Overflow\n");
    exit(0); //Terminate program execution
  }

}

void deleteNode(struct Node**root,int element)
{
  if(root == NULL)
  {
    //When BST are no have elements
    printf("Empty Binary Search Tree\n");
  }
  else
  {

    struct Node*find = *root,*parent=NULL;

    while(find!=NULL)
    {
      if(find->data > element)
      {
        parent=find;
        find=find->left;
      }
      else if(find->data < element)
      {
        parent=find;
        find=find->right;
      }
      else
      {
        //when delete node exists
        break;
      }
    }

    if(find!=NULL && find->data == element)
    {
      printf("\n Delete node : %d\n",element );
      //when confirmed delete nodes is exist

      if(parent==NULL)
      {
        //when delete root node

        if(find->left == NULL && find->right == NULL)
        {
          find=NULL;
          free(*root);
          *root=NULL;
          return;
        }
        else if(find->right == NULL)
        {
            
          *root = find->left;
          free(find);
          find=NULL;
          return;
        }
        else if(find->left == NULL)
        {
          *root = find->right;
          free(find);
          find=NULL;
          return;
        }
      }

      if(parent!=NULL && (find->left == NULL && find->right == NULL))
      {
        
        //delete leaf node

        if(parent->left == find)
        {
          parent->left = NULL;
        }
        else
        {
          parent->right = NULL;
        }

        free(find);

        find=NULL;
        return;
      }
      else if(parent!=NULL && find->right == NULL)
      {
        

        if(parent->left == find)
        {
          parent->left = find->left;
        }
        else
        {
          parent->right = find->left;
        }

        free(find);

        find=NULL;
        return;
      }

      parent=find;

      find=find->right;

      if(find->left==NULL)
      {
        parent->data=find->data;
        parent->right=find->right;
        free(find);
        find=NULL;
        return;
      }

      while(find->left!=NULL && find->left->left!=NULL)
      {
        find=find->left;
      }  
      if(find->left!=NULL)
      {
        parent->data=find->left->data; 
        parent=find->left;
        find->left=parent->right;
        free(parent);
        parent=NULL;
      }

    }
    else
    {
      printf("\n  Delete element not exist %d\n",element );
    }

  }
}
void preorder(struct Node*root)
{
  if(root!=NULL)
  {
    printf("%3d ",root->data );
    preorder(root->left);

    preorder(root->right);
  }
}
int main(){
    
  struct Node*root = NULL;

  //Add nodes in binary search tree
  /*
          7
        /   \
       4     10
      / \   /
     3   5 8
            \
             9
  */

  add(&root,7);
  add(&root,4);
  add(&root,3);
  add(&root,5);
  add(&root,10);
  add(&root,8);
  add(&root,9);

  preorder(root);
  //Test case
  deleteNode(&root,7);
  preorder(root);

  deleteNode(&root,4);
  preorder(root);

  deleteNode(&root,10);
  preorder(root);
 
  deleteNode(&root,8);
  preorder(root);
  return 0;
}

Output

  7   4   3   5  10   8   9 
 Delete node : 7
  8   4   3   5  10   9 
 Delete node : 4
  8   5   3  10   9 
 Delete node : 10
  8   5   3   9 
 Delete node : 8
  9   5   3
//C++ Program 
//Delete a node in binary search tree
#include <iostream>
using namespace std;
//structure of Binary Search Tree node
struct Node

{
  int data;
  struct Node *left,*right; 
};
class BST
{

public:
  Node*root;
  BST();
  //public methods
  void add(int);
  void delete_node(int);
  void preorder(Node*);

};
BST::BST()
{
  root=NULL;
}
//Adding a new node in binary search tree
void BST :: add(int data)
{
  //Create a dynamic node of binary search tree 
   Node *new_node = new Node();

  if(new_node!=NULL)
  {
    //Set data and pointer values
    new_node->data = data;
    new_node->left = NULL; //Initially node left-pointer is NULL
    new_node->right = NULL;//Initially node right-pointer is NULL

    if(root == NULL)
    {
      //When adds a first node in binary tree
      root = new_node;
    }
    else
    {
       Node *find = root;

      //add new node to proper position
      while(find != NULL)
      {
        if(find -> data >= data)
        { 
          if(find->left==NULL)
          {
            find->left = new_node;
            break;
          }
          else
          { 
            //visit left sub-tree
            find = find->left;
          }
        }
        else
        {
          if(find->right == NULL)
          {
            find->right = new_node;
            break;
          }
          else
          {
            //visit right sub-tree
            find = find->right;
          }
        }
      }
    }
  }
  else
  {
    cout<<("Memory Overflow\n");
  }
}
//Remove given node element in BST
void BST:: delete_node(int element)
{
  if(root == NULL)
  {
    //When BST are no have elements
    cout<<"Empty Binary Search Tree\n";
  }
  else
  {

     Node*find = root,*parent=NULL;

    while(find!=NULL)
    {
      if(find->data > element)
      {
        parent=find;
        find=find->left;
      }
      else if(find->data < element)
      {
        parent=find;
        find=find->right;
      }
      else
      {
        //when delete node exists
        break;
      }
    }

    if(find!=NULL && find->data == element)
    {
      cout<<"\n Delete node : "<< element<<endl;
      //when confirmed delete nodes is exist

      if(parent==NULL)
      {
        //when delete root node

        if(find->left == NULL && find->right == NULL)
        {
          find=NULL;
          delete root;
          root=NULL;
          return;
        }
        else if(find->right == NULL)
        {
            
          root = find->left;
          delete (find);
          find=NULL;
          return;
        }
        else if(find->left == NULL)
        {
          root = find->right;
          delete find;
          find=NULL;
          return;
        }
      }

      if(parent!=NULL && (find->left == NULL && find->right == NULL))
      {
        
        //delete leaf node

        if(parent->left == find)
        {
          parent->left = NULL;
        }
        else
        {
          parent->right = NULL;
        }

        delete find;

        find=NULL;
        return;
      }
      else if(parent!=NULL && find->right == NULL)
      {
        

        if(parent->left == find)
        {
          parent->left = find->left;
        }
        else
        {
          parent->right = find->left;
        }

        delete find;

        find=NULL;
        return;
      }

      parent=find;

      find=find->right;

      if(find->left==NULL)
      {
        parent->data=find->data;
        parent->right=find->right;
        delete find;
        find=NULL;
        return;
      }

      while(find->left!=NULL && find->left->left!=NULL)
      {
        find=find->left;
      }  
      if(find->left!=NULL)
      {
        parent->data=find->left->data; 
        parent=find->left;
        find->left=parent->right;
        delete parent;
        parent=NULL;
      }

    }
    else
    {
      cout<<"\n  Delete element not exist "<< element <<endl;
    }

  }
}
void BST :: preorder(Node*root)
{
  if(root!=NULL)
  {
    cout<<"  "<< root->data;
    preorder(root->left);

    preorder(root->right);
  }
}
int main()
{

  BST obj;

  //Add nodes in binary search tree
  /*
          7
        /   \
       4     10
      / \   /
     3   5 8
            \
             9
  */

  obj.add(7);
  obj.add(4);
  obj.add(3);
  obj.add(5);
  obj.add(10);
  obj.add(8);
  obj.add(9);

  obj.preorder(obj.root);
  //Test case
  obj.delete_node(7);
  obj.preorder(obj.root);

  obj.delete_node(4);
  obj.preorder(obj.root);

  obj.delete_node(10);
  obj.preorder(obj.root);
 
  obj.delete_node(8);
  obj.preorder(obj.root);

  return 0;
}

Output

  7  4  3  5  10  8  9
 Delete node : 7
  8  4  3  5  10  9
 Delete node : 4
  8  5  3  10  9
 Delete node : 10
  8  5  3  9
 Delete node : 8
  9  5  3
//Java program
//Delete a node in binary search tree
public class BST
{

  static class Node
  {
    int data;
    Node left,right;
  }
  public Node root;
  //Class constructors
  BST()
  {
    root=null;
   
  } 

  //insert  element
  public void add(int data)
  {
    //Create a dynamic node of binary search tree 
    Node new_node = new Node();

    if(new_node != null)
    {
      //Set data and pointer values
      new_node.data = data;
      //Initially node left-pointer is null
      new_node.left = null; 
      //Initially node right-pointer is null
      new_node.right = null;

      if(root == null)
      {
        //When adds a first node in binary tree
        root = new_node;
      }
      else
      {
        Node find = root;

        //add new node to proper position
        while(find != null)
        {
          if(find.data >= data)
          { 
            if(find.left==null)
            {
              find.left = new_node;
              break;
            }
            else
            { 
              //visit left sub-tree
              find = find.left;
            }
          }
          else
          {
            if(find.right == null)
            {
              find.right = new_node;
              break;
            }
            else
            {
              //visit right sub-tree
              find = find.right;
            }
          }
        }
      }
    }
    else
    {
      System.out.println("Memory Overflow");
    }
  }
//Remove given node element in BST
public void  delete_node(int element)
{
  if(root == null)
  {
    //When BST are no have elements
    System.out.println("Empty Binary Search Tree");
  }
  else
  {

     Node find = root, parent=null;

    while(find!=null)
    {
      if(find.data > element)
      {
        parent=find;
        find=find.left;
      }
      else if(find.data < element)
      {
        parent=find;
        find=find.right;
      }
      else
      {
        //when delete node exists
        break;
      }
    }

    if(find!=null && find.data == element)
    {
      System.out.println("\n Delete node : "+ element);
      //when confirmed delete nodes is exist

      if(parent==null)
      {
        //when delete root node

        if(find.left == null && find.right == null)
        {
          find=null;
          root=null;
          return;
        }
        else if(find.right == null)
        {
            
          root = find.left;
          find=null;
          return;
        }
        else if(find.left == null)
        {
          root = find.right;
          find=null;
          return;
        }
      }

      if(parent!=null && (find.left == null && find.right == null))
      {
        
        //delete leaf node

        if(parent.left == find)
        {
          parent.left = null;
        }
        else
        {
          parent.right = null;
        }

        find=null;
        return;
      }
      else if(parent!=null && find.right == null)
      {
        

        if(parent.left == find)
        {
          parent.left = find.left;
        }
        else
        {
          parent.right = find.left;
        }


        find=null;
        return;
      }

      parent=find;

      find=find.right;

      if(find.left==null)
      {
        parent.data=find.data;
        parent.right=find.right;
        find=null;
        return;
      }

      while(find.left!=null && find.left.left!=null)
      {
        find=find.left;
      }  
      if(find.left!=null)
      {
        parent.data=find.left.data; 
        parent=find.left;
        find.left=parent.right;
        parent=null;
      }

    }
    else
    {
      System.out.println("\n  Delete element not exist "+ element );
    }

  }
}
  public void preorder(Node root)
  {
    if(root!=null)
    {
      System.out.print("  "+ root.data);
      preorder(root.left);

      preorder(root.right);
    }
  }

  public static void main(String[] args) 
  {

    BST obj = new BST();

  //Add nodes in binary search tree
  /*
          7
        /   \
       4     10
      / \   /
     3   5 8
            \
             9
  */

  obj.add(7);
  obj.add(4);
  obj.add(3);
  obj.add(5);
  obj.add(10);
  obj.add(8);
  obj.add(9);

  obj.preorder(obj.root);
  //Test case
  obj.delete_node(7);
  obj.preorder(obj.root);

  obj.delete_node(4);
  obj.preorder(obj.root);

  obj.delete_node(10);
  obj.preorder(obj.root);
 
  obj.delete_node(8);
  obj.preorder(obj.root);


    }
}

Output

  7  4  3  5  10  8  9
 Delete node : 7
  8  4  3  5  10  9
 Delete node : 4
  8  5  3  10  9
 Delete node : 10
  8  5  3  9
 Delete node : 8
  9  5  3
#Python Program 
#Delete a node in binary search tree
class Node:
  def __init__(self,data):
    self.data=data
    self.left=None
    self.right=None

   
class BST:

  def __init__(self):

    #Assign default value
    self.root=None
  
  #insert  element
  def add(self,data):

    #Create a dynamic node of binary search tree 
    new_node = Node(data)

    if(self.root == None):
      #When adds a first node in binary tree
      self.root = new_node
    
    else:
      find = self.root

      #add new node to proper position
      while(find != None):

        if(find.data >= data): 

          if(find.left==None):

            find.left = new_node
            break
          
          else: 

            #visit left sub-tree
            find = find.left
          
        
        else:

          if(find.right == None):

            find.right = new_node
            break
          
          else:

            #visit right sub-tree
            find = find.right

  def preorder(self, root):

    if(root!=None):

      print(root.data,end="  ")
      self.preorder(root.left)

      self.preorder(root.right)  
  #Remove given node element in BST
  def delete_node(self,element):
    
    if(self.root == None) :

      #When BST are no have elements
      print("Empty Binary Search Tree")
    
    else :

      find = self.root
      parent=None

      while(find!=None):

        if(find.data > element):

          parent=find
          find=find.left
        
        elif(find.data < element):

          parent=find
          find=find.right
        
        else:

          #when delete node exists
          break
        
      

      if(find!=None  and  find.data == element):

        print("\n Delete node : ", element)
        #when confirmed delete nodes is exist

        if(parent==None):

          #when delete root node

          if(find.left == None  and  find.right == None):

            find=None
            self.root=None
            return
          
          elif(find.right == None):
              
            self.root = find.left
            find=None
            return
          
          elif(find.left == None):
            self.root = find.right
            find=None
            return
          
        

        if(parent!=None  and  (find.left == None  and  find.right == None)):

          
          #delete leaf node

          if(parent.left == find):

            parent.left = None
          
          else :
            parent.right = None
          

          find=None
          return
        
        elif(parent!=None  and  find.right == None):
          

          if(parent.left == find):

            parent.left = find.left
          
          else :
            parent.right = find.left
          


          find=None
          return
        

        parent=find

        find=find.right

        if(find.left==None) :
          parent.data=find.data
          parent.right=find.right
          find=None
          return
        

        while(find.left!=None  and  find.left.left!=None) :
          find=find.left
          
        if(find.left!=None):
          parent.data=find.left.data 
          parent=find.left
          find.left=parent.right
          parent=None
        

      
      else :
        print("\n  Delete element not exist ", element )
      

  

def main():

  obj = BST()


  #Add nodes in binary search tree
  #
  #        7
  #      /   \
  #     4     10
  #    / \   /
  #   3   5 8
  #          \
  #           9
  #

  obj.add(7);
  obj.add(4);
  obj.add(3);
  obj.add(5);
  obj.add(10);
  obj.add(8);
  obj.add(9);

  obj.preorder(obj.root);
  #Test case
  obj.delete_node(7);
  obj.preorder(obj.root);

  obj.delete_node(4);
  obj.preorder(obj.root);

  obj.delete_node(10);
  obj.preorder(obj.root);
 
  obj.delete_node(8);
  obj.preorder(obj.root);

if __name__ =="__main__":
  main()

Output

7  4  3  5  10  8  9  
 Delete node :  7
8  4  3  5  10  9  
 Delete node :  4
8  5  3  10  9  
 Delete node :  10
8  5  3  9  
 Delete node :  8
9  5  3  
//C# program
//Delete a node in binary search tree
using System;
public class Node
{
  public int data;
  public Node left,right;
}
public class BST
{


  public Node root;
  //Class constructors
  BST()
  {
    root=null;

  } 

  //insert  element
  public void add(int data)
  {
    //Create a dynamic node of binary search tree 
    Node new_node = new Node();

    if(new_node != null)
    {
      //Set data and pointer values
      new_node.data = data;
      //Initially node left-pointer is null
      new_node.left = null; 
      //Initially node right-pointer is null
      new_node.right = null;

      if(root == null)
      {
        //When adds a first node in binary tree
        root = new_node;
      }
      else
      {
        Node find = root;

        //add new node to proper position
        while(find != null)
        {
          if(find.data >= data)
          { 
            if(find.left==null)
            {
              find.left = new_node;
              break;
            }
            else
            { 
              //visit left sub-tree
              find = find.left;
            }
          }
          else
          {
            if(find.right == null)
            {
              find.right = new_node;
              break;
            }
            else
            {
              //visit right sub-tree
              find = find.right;
            }
          }
        }
      }
    }
    else
    {
      Console.WriteLine("Memory Overflow");
    }
  }
  //Remove given node element in BST
  public void  delete_node(int element)
  {
    if(root == null)
    {
      //When BST are no have elements
      Console.WriteLine("Empty Binary Search Tree");
    }
    else
    {

      Node find = root, parent=null;

      while(find!=null)
      {
        if(find.data > element)
        {
          parent=find;
          find=find.left;
        }
        else if(find.data < element)
        {
          parent=find;
          find=find.right;
        }
        else
        {
          //when delete node exists
          break;
        }
      }

      if(find!=null && find.data == element)
      {
        Console.WriteLine("\n Delete node : "+ element);
        //when confirmed delete nodes is exist

        if(parent==null)
        {
          //when delete root node

          if(find.left == null && find.right == null)
          {
            find=null;
            root=null;
            return;
          }
          else if(find.right == null)
          {

            root = find.left;
            find=null;
            return;
          }
          else if(find.left == null)
          {
            root = find.right;
            find=null;
            return;
          }
        }

        if(parent!=null && (find.left == null && find.right == null))
        {

          //delete leaf node

          if(parent.left == find)
          {
            parent.left = null;
          }
          else
          {
            parent.right = null;
          }

          find=null;
          return;
        }
        else if(parent!=null && find.right == null)
        {


          if(parent.left == find)
          {
            parent.left = find.left;
          }
          else
          {
            parent.right = find.left;
          }


          find=null;
          return;
        }

        parent=find;

        find=find.right;

        if(find.left==null)
        {
          parent.data=find.data;
          parent.right=find.right;
          find=null;
          return;
        }

        while(find.left!=null && find.left.left!=null)
        {
          find=find.left;
        }  
        if(find.left!=null)
        {
          parent.data=find.left.data; 
          parent=find.left;
          find.left=parent.right;
          parent=null;
        }

      }
      else
      {
        Console.WriteLine("\n  Delete element not exist "+ element );
      }

    }
  }
  public void preorder(Node root)
  {
    if(root!=null)
    {
      Console.Write("  "+ root.data);
      preorder(root.left);

      preorder(root.right);
    }
  }

  public static void Main(String[] args) 
  {

    BST obj = new BST();

    //Add nodes in binary search tree
    /*
          7
        /   \
       4     10
      / \   /
     3   5 8
            \
             9
  */

    obj.add(7);
    obj.add(4);
    obj.add(3);
    obj.add(5);
    obj.add(10);
    obj.add(8);
    obj.add(9);

    obj.preorder(obj.root);
    //Test case
    obj.delete_node(7);
    obj.preorder(obj.root);

    obj.delete_node(4);
    obj.preorder(obj.root);

    obj.delete_node(10);
    obj.preorder(obj.root);

    obj.delete_node(8);
    obj.preorder(obj.root);


  }
}

Output

  7  4  3  5  10  8  9
 Delete node : 7
  8  4  3  5  10  9
 Delete node : 4
  8  5  3  10  9
 Delete node : 10
  8  5  3  9
 Delete node : 8
  9  5  3

<?php
//Php program 
//Delete a node in binary search tree
class Node
{
  public $data;
  public $left;
  public $right;
  function __construct($data)
  {
    $this->data = $data;
    $this->length = NULL;
    $this->right = NULL;
  }
}
class BST
{

  public $root;

  function __construct()
  {
    $root=NULL;
  }

 //Adding a new node in binary search tree
  function add($data)
  {
    //Create a dynamic node of binary search tree 
    $new_node = new Node($data);

    if($this->root == NULL)
    {
      //When adds a first node in binary tree
      $this->root = $new_node;
    }
    else
    {
      $find = $this->root;

      //add new node to proper position
      while($find != NULL)
      {
        if($find->data >= $data)
        { 
          if($find->left==NULL)
          {
            $find->left = $new_node;
            break;
          }
          else
          { 
          //visit left sub-tree
            $find = $find->left;
          }
        }
        else
        {
          if($find->right == NULL)
          {
            $find->right = $new_node;
            break;
          }
          else
          {
          //visit right sub-tree
            $find = $find->right;
          }
        }
      }
    }

  }
  function preorder($root)
  {
    if($root!=NULL)
    {
      echo "  ". $root->data;
      $this->preorder($root->left);

      $this->preorder($root->right);
    }
  }

   //Remove given node element in BST
  function delete_node($element)
  {
    if($this->root == NULL)
    {
      //When BST are no have elements
      echo "Empty Binary Search Tree\n";
    }
    else
    {

     $find = $this->root;
     $parent=NULL;

     while($find!=NULL)
     {
      if($find->data > $element)
      {
        $parent=$find;
        $find=$find->left;
      }
      else if($find->data < $element)
      {
        $parent=$find;
        $find=$find->right;
      }
      else
      {
        //when delete node exists
        break;
      }
    }

    if($find!=NULL && $find->data == $element)
    {
      echo "\n Delete node : $element\n";
      //when confirmed delete nodes is exist

      if($parent==NULL)
      {
        //when delete root node

        if($find->left == NULL && $find->right == NULL)
        {
          $find=NULL;

          $this->root=NULL;
          return;
        }
        else if($find->right == NULL)
        {

          $this->root = $find->left;
          
          $find=NULL;
          return;
        }
        else if($find->left == NULL)
        {
          $this->root = $find->right;

          $find=NULL;
          return;
        }
      }

      if($parent!=NULL && ($find->left == NULL && $find->right == NULL))
      {

        //delete leaf node

        if($parent->left == $find)
        {
          $parent->left = NULL;
        }
        else
        {
          $parent->right = NULL;
        }


        $find=NULL;
        return;
      }
      else if($parent!=NULL && $find->right == NULL)
      {


        if($parent->left == $find)
        {
          $parent->left = $find->left;
        }
        else
        {
          $parent->right = $find->left;
        }


        $find=NULL;
        return;
      }

      $parent=$find;

      $find=$find->right;

      if($find->left==NULL)
      {
        $parent->data=$find->data;
        $parent->right=$find->right;

        $find=NULL;
        return;
      }

      while($find->left!=NULL && $find->left->left!=NULL)
      {
        $find=$find->left;
      }  
      if($find->left!=NULL)
      {
        $parent->data=$find->left->data; 
        $parent=$find->left;
        $find->left=$parent->right;

        $parent=NULL;
      }

    }
    else
    {
      echo "\n  Delete element not exist ".$element ;
    }

  }
}
}
function main()
{
  //Make a object of BST class
  $obj= new BST();

   //Add nodes in binary search tree
  /*
          7
        /   \
       4     10
      / \   /
     3   5 8
            \
             9
  */

  $obj->add(7);
  $obj->add(4);
  $obj->add(3);
  $obj->add(5);
  $obj->add(10);
  $obj->add(8);
  $obj->add(9);

  $obj->preorder($obj->root);
  //Test case
  $obj->delete_node(7);
  $obj->preorder($obj->root);

  $obj->delete_node(4);
  $obj->preorder($obj->root);

  $obj->delete_node(10);
  $obj->preorder($obj->root);

  $obj->delete_node(8);
  $obj->preorder($obj->root);
}
main();
?>

Output

  7  4  3  5  10  8  9
 Delete node : 7
  8  4  3  5  10  9
 Delete node : 4
  8  5  3  10  9
 Delete node : 10
  8  5  3  9
 Delete node : 8
  9  5  3
# Ruby Program
# Delete a node in binary search tree

class Node 
  attr_reader :data, :left, :right
  attr_accessor :data, :left, :right
  def initialize(value) 
    @data = value
    @left = nil
    @right = nil
  end
end

class BinarySearchTree 
  attr_reader :root
  attr_accessor :root
  def initialize() 
    @root = nil
  end
  def add(value) 
    new_node = Node.new(value)
    if (new_node != nil) 
      if (@root == nil) 
        @root = new_node
      else 
        find = @root
        while (find != nil) 
          if (find.data >= value) 
            if (find.left == nil) 
              find.left = new_node
              break
            else 
              find = find.left
            end
          else 
            if (find.right == nil) 
              find.right = new_node
              break
            else 
              find = find.right
            end
          end
        end
      end
    else 
      print("\nMemory Overflow\n")
    end
  end
  def delete_node(element) 
    if (@root == nil) 
      print("Empty Binary Search Tree")
    else 
      find = @root
      parent = nil
      while (find != nil) 
        if (find.data > element) 
          parent = find
          find = find.left
        elsif (find.data < element) 
          parent = find
          find = find.right
        else 
          break
        end
      end
      if (find != nil and find.data == element) 
        print("\n Delete node  :", element,"\n")
        if (parent == nil) 
          if (find.left == nil and find.right == nil) 
            find = nil
            @root = nil
            return
          elsif (find.right == nil) 
            @root = find.left
            find = nil
            return
          elsif (find.left == nil) 
            @root = find.right
            find = nil
            return
          end
        end
        if (parent != nil and(find.left == nil and find.right == nil)) 
          if (parent.left == find) 
            parent.left = nil
          else 
            parent.right = nil
          end
          find = nil
          return
        elsif (parent != nil and find.right == nil) 
          if (parent.left == find) 
            parent.left = find.left
          else 
            parent.right = find.left
          end
          find = nil
          return
        end
        parent = find
        find = find.right
        if (find.left == nil) 
          parent.data = find.data
          parent.right = find.right
          find = nil
          return
        end
        while (find.left != nil and find.left.left != nil) 
          find = find.left
        end
        if (find.left != nil) 
          parent.data = find.left.data
          parent = find.left
          find.left = parent.right
          parent = nil
        end
      else 
        print("\n  Delete element not exist ", element,"\n")
      end
    end
  end
  def preorder(head) 
    if (head != nil) 
      print("  ", head.data)
      self.preorder(head.left)
      self.preorder(head.right)
    end
  end
end
def main() 
  obj = BinarySearchTree.new()
  #Add nodes in binary search tree
  #
  #        7
  #      /   \
  #     4     10
  #    / \   /
  #   3   5 8
  #          \
  #           9
  #
  obj.add(7)
  obj.add(4)
  obj.add(3)
  obj.add(5)
  obj.add(10)
  obj.add(8)
  obj.add(9)
  obj.preorder(obj.root)
  obj.delete_node(7)
  obj.preorder(obj.root)
  obj.delete_node(4)
  obj.preorder(obj.root)
  obj.delete_node(10)
  obj.preorder(obj.root)
  obj.delete_node(8)
  obj.preorder(obj.root)
end

main()

Output

  7  4  3  5  10  8  9
 Delete node  :7
  8  4  3  5  10  9
 Delete node  :4
  8  5  3  10  9
 Delete node  :10
  8  5  3  9
 Delete node  :8
  9  5  3
/*
  Node Js Program
  Delete a node in binary search tree
*/

class Node {
  
  constructor(value) {
    this.data = value;
    this.left = null;
    this.right = null;
  }
}
class BinarySearchTree {
  
  constructor() {
    this.root = null;
  }
  add(value) {
    var new_node = new Node(value);
    if (new_node != null) {
      if (this.root == null) {
        this.root = new_node;
      } else {
        var find = this.root;
        while (find != null) {
          if (find.data >= value) {
            if (find.left == null) {
              find.left = new_node;
              break;
            } else {
              find = find.left;
            }
          } else {
            if (find.right == null) {
              find.right = new_node;
              break;
            } else {
              find = find.right;
            }
          }
        }
      }
    } else {
      process.stdout.write("\nMemory Overflow\n");
    }
  }
  delete_node(element) {
    if (this.root == null) {
      process.stdout.write("Empty Binary Search Tree");
    } else {
      var find = this.root;
      var parent = null;
      while (find != null) {
        if (find.data > element) {
          parent = find;
          find = find.left;
        } else
        if (find.data < element) {
          parent = find;
          find = find.right;
        } else {
          break;
        }
      }
      if (find != null && find.data == element) {
        process.stdout.write("\n Delete node : " + element+"\n");
        if (parent == null) {
          if (find.left == null && find.right == null) {
            find = null;
            this.root = null;
            return;
          } else
          if (find.right == null) {
            this.root = find.left;
            find = null;
            return;
          } else
          if (find.left == null) {
            this.root = find.right;
            find = null;
            return;
          }
        }
        if (parent != null && (find.left == null && find.right == null)) {
          if (parent.left == find) {
            parent.left = null;
          } else {
            parent.right = null;
          }
          find = null;
          return;
        } else
        if (parent != null && find.right == null) {
          if (parent.left == find) {
            parent.left = find.left;
          } else {
            parent.right = find.left;
          }
          find = null;
          return;
        }
        parent = find;
        find = find.right;
        if (find.left == null) {
          parent.data = find.data;
          parent.right = find.right;
          find = null;
          return;
        }
        while (find.left != null && find.left.left != null) {
          find = find.left;
        }
        if (find.left != null) {
          parent.data = find.left.data;
          parent = find.left;
          find.left = parent.right;
          parent = null;
        }
      } else {
        process.stdout.write("\n  Delete element not exist " + element);
      }
    }
  }
  preorder(head) {
    if (head != null) {
      process.stdout.write("  " + head.data);
      this.preorder(head.left);
      this.preorder(head.right);
    }
  }
}

function main() {
  var obj = new BinarySearchTree();
  //Add nodes in binary search tree
  /*
        7
      /   \
     4     10
    / \   /
   3   5 8
          \
           9
  */

  obj.add(7);
  obj.add(4);
  obj.add(3);
  obj.add(5);
  obj.add(10);
  obj.add(8);
  obj.add(9);
  obj.preorder(obj.root);
  obj.delete_node(7);
  obj.preorder(obj.root);
  obj.delete_node(4);
  obj.preorder(obj.root);
  obj.delete_node(10);
  obj.preorder(obj.root);
  obj.delete_node(8);
  obj.preorder(obj.root);
}

main();

Output

  7  4  3  5  10  8  9
 Delete node  :7
  8  4  3  5  10  9
 Delete node  :4
  8  5  3  10  9
 Delete node  :10
  8  5  3  9
 Delete node  :8
  9  5  3
/*
Swift 3 program
Delete a node in binary search tree

*/

class Node {
  var data: Int;
  var left: Node? ;
  var right: Node? ;
  init(_ value: Int) {
    self.data = value;
    self.left = nil;
    self.right = nil;
  }
}
class BinarySearchTree {
  var root: Node? ;
  init() {
    self.root = nil;
  }
  func add(_ value: Int) {
    let new_node: Node? = Node(value);
    if (new_node != nil) {
      if (self.root == nil) {
        self.root = new_node;
      } else {
        var find: Node? = self.root;
        while (find != nil) {
          if (find!.data >= value) {
            if (find!.left == nil) {
              find!.left = new_node;
              break;
            } else {
              find = find!.left;
            }
          } else {
            if (find!.right == nil) {
              find!.right = new_node;
              break;
            } else {
              find = find!.right;
            }
          }
        }
      }
    } else {
      print("\nMemory Overflow\n");
    }
  }
  func delete_node(_ element: Int) {
    if (self.root == nil) {
      print("Empty Binary Search Tree");
    } else {
      var find: Node? = self.root;
      var parent: Node? = nil;
      while (find != nil) {
        if (find!.data > element) {
          parent = find;
          find = find!.left;
        } else
        if (find!.data < element) {
          parent = find;
          find = find!.right;
        } else {
          break;
        }
      }
      if (find != nil && find!.data == element) {
        print("\n Delete node : ", element);
        if (parent == nil) {
          if (find!.left == nil && find!.right == nil) {
            find = nil;
            self.root = nil;
            return;
          } else
          if (find!.right == nil) {
            self.root = find!.left;
            find = nil;
            return;
          } else
          if (find!.left == nil) {
            self.root = find!.right;
            find = nil;
            return;
          }
        }
        if (parent != nil && (find!.left == nil && find!.right == nil)) {
          if (parent!.left === find) {
            parent!.left = nil;
          } else {
            parent!.right = nil;
          }
          find = nil;
          return;
        } else
        if (parent != nil && find!.right == nil) {
          if (parent!.left === find) {
            parent!.left = find!.left;
          } else {
            parent!.right = find!.left;
          }
          find = nil;
          return;
        }
        parent = find;
        find = find!.right;
        if (find!.left == nil) {
          parent!.data = find!.data;
          parent!.right = find!.right;
          find = nil;
          return;
        }
        while (find!.left != nil && find!.left!.left != nil) {
          find = find!.left;
        }
        if (find!.left != nil) {
          parent!.data = find!.left!.data;
          parent = find!.left;
          find!.left = parent!.right;
          parent = nil;
        }
      } else {
        print("\n  Delete element not exist ", element);
      }
    }
  }
  func preorder(_ head: Node? ) {
    if (head != nil) {
      print(" ", head!.data,terminator:"");
      self.preorder(head!.left);
      self.preorder(head!.right);
    }
  }
}
func main() {
  let obj: BinarySearchTree = BinarySearchTree();
  //Add nodes in binary search tree
  /*
          7
        /   \
       4     10
      / \   /
     3   5 8
            \
             9
  */

  obj.add(7);
  obj.add(4);
  obj.add(3);
  obj.add(5);
  obj.add(10);
  obj.add(8);
  obj.add(9);
  obj.preorder(obj.root);
  obj.delete_node(7);
  obj.preorder(obj.root);
  obj.delete_node(4);
  obj.preorder(obj.root);
  obj.delete_node(10);
  obj.preorder(obj.root);
  obj.delete_node(8);
  obj.preorder(obj.root);
}
main();

Output

  7  4  3  5  10  8  9
 Delete node  :7
  8  4  3  5  10  9
 Delete node  :4
  8  5  3  10  9
 Delete node  :10
  8  5  3  9
 Delete node  :8
  9  5  3
Last updated on by Kalkicode




Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment