Posted on by Kalkicode
Code Binary Search Tree

Delete nodes which are greater than or equal to given value in BST

Delete nodes which are greater than or equal to value

Here given code implementation process.

//C Program 
//Delete nodes which are greater than or equal to given value in BST
#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 swap_data(struct Node*root1,struct Node*root2)
{
  int temp=root2->data;
  root2->data=root1->data;
  root1->data=temp;
}

struct Node* remove_node(struct Node*root,int key)
{
  if(root != NULL)
  {
   
      root->right = remove_node(root->right,key);

      root->left = remove_node(root->left,key);
    
          
 
    
    struct Node*temp=NULL,*back=NULL;
    if(root->data >= key)
    {
      if(root->left==NULL)
      {
        temp=root;
        root=root->right;
      }
      else if(root->right==NULL)
      {
        temp=root;
        root=root->left;
      }
      else
      {
        temp=root->left;
        back=root;
        while(temp->right!=NULL)
        {
          back=temp;
          temp=temp->right;
        }
        if(root->left==temp)
        {
          swap_data(root,temp);
          root->left=temp->left;
        }
        else{
          swap_data(root,temp);
          back->right=temp->left;
        }
      }

      if(temp!=NULL)
      {
        free(temp);
        temp=NULL;
      }
    }

  }
  return root;
}

struct Node* delete_node(struct Node*root,int key)
{
  if(root!=NULL)
  {

    
    root=remove_node(root,key);

  }
  else
  {
    printf("\n  Empty BST\n");
  }
  printf("\n");
  return root;
}
void inorder(struct Node*root)
{
  if(root!=NULL)
  {

    inorder(root->left);
    printf("%3d ",root->data );
    inorder(root->right);
  }
}
int main(){

  struct Node*root = NULL;

  //Add nodes in binary search tree
  /*
              5
            /   \ 
           /     \
          3       19
         / \     /  \
        2   4   8    31
       /       / \    /
      1       7   15  25   


  */                

  add(&root,5); 
  add(&root,3); 
  add(&root,19); 
  add(&root,2); 
  add(&root,4); 
  add(&root,8); 
  add(&root,31); 
  add(&root,1); 
  add(&root,7); 
  add(&root,25); 
  add(&root,15); 


  inorder(root);

  root=delete_node(root,8);

  /*
    After delete nodes 
    -----------------
              5
            /   \ 
           /     \
          3       7
         / \    
        2   4  
       /           
      1             
  */
  inorder(root);
  return 0;
}

Output

  1   2   3   4   5   7   8  15  19  25  31 
  1   2   3   4   5   7
/*
 C++ Program
 Delete nodes which are greater than or equal to given value in BST
*/

#include <iostream>

using namespace std;
class Node {
public:
  int data;
  Node *left;
  Node *right;
  Node(int value) {
    this->data = value;
    this->left = NULL;
    this->right = NULL;
  }
};
class BinarySearchTree {
public:
  Node *root;
  BinarySearchTree() {
    this->root = NULL;
  }
  void add(int value) {
    Node *new_node = new Node(value);
    if (new_node != NULL) {
      if (this->root == NULL) {
        this->root = new_node;
      } else {
        Node *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 {
      cout << "\nMemory Overflow\n";
    }
  }
  void inorder(Node *head) {
    if (head != NULL) {
      this->inorder(head->left);
      cout << head->data << "  ";
      this->inorder(head->right);
    }
  }
  void swap_data(Node *root1, Node *root2) {
    int temp = root2->data;
    root2->data = root1->data;
    root1->data = temp;
  }
  Node *remove_node(Node *head, int key) {
    if (head != NULL) {
      head->right = this->remove_node(head->right, key);
      head->left = this->remove_node(head->left, key);
      Node *temp = NULL, *back = NULL;
      if (head->data >= key) {
        if (head->left == NULL) {
          temp = head;
          head = head->right;
        } else
        if (head->right == NULL) {
          temp = head;
          head = head->left;
        } else {
          temp = head->left;
          back = head;
          while (temp->right != NULL) {
            back = temp;
            temp = temp->right;
          }
          if (head->left == temp) {
            this->swap_data(head, temp);
            head->left = temp->left;
          } else {
            this->swap_data(head, temp);
            back->right = temp->left;
          }
        }
        temp = NULL;
      }
    }
    return head;
  }
  void delete_keys(int key) {
    if (this->root != NULL) {
      this->root = this->remove_node(this->root, key);
    } else {
      cout << "\n  Empty BST\n";
    }
    cout << "\n";
  }
};

int main() {
  BinarySearchTree obj ;
  /*
              5
            /   \ 
           /     \
          3       19
         / \     /  \
        2   4   8    31
       /       / \    /
      1       7   15  25   


  */   
  obj.add(5);
  obj.add(3);
  obj.add(19);
  obj.add(2);
  obj.add(4);
  obj.add(8);
  obj.add(31);
  obj.add(1);
  obj.add(7);
  obj.add(25);
  obj.add(15);
  obj.inorder(obj.root);
  obj.delete_keys(8);
    /*
    After delete nodes 
    -----------------
              5
            /   \ 
           /     \
          3       7
         / \    
        2   4  
       /           
      1             
  */
  obj.inorder(obj.root);
  return 0;
}

Output

  1   2   3   4   5   7   8  15  19  25  31 
  1   2   3   4   5   7
//Java program
//Delete nodes which are greater than or equal to given value in BST

//BST node
class Node {

  public int data;
  public Node left;
  public Node right;

  public Node(int value) {
    data = value;
    left = null;
    right = null;
  }
}
public class BinarySearchTree {


  public Node root;


  public BinarySearchTree() {
    root = null;

  }
  //insert a node in BST
  public void add(int value) {
    //Create a dynamic node of binary search tree 
    Node new_node = new Node(value);

    if (new_node != 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 >= value) {
            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.print("\nMemory Overflow\n");
    }
  }

  public void inorder(Node head) {
    if (head != null) {

      inorder(head.left);
      System.out.print(head.data + "  ");
      inorder(head.right);
    }
  }

  public void swap_data(Node root1, Node root2) {
    int temp = root2.data;
    root2.data = root1.data;
    root1.data = temp;
  }
  public Node  remove_node(Node head,int key)
{
  if(head != null)
  {
   
      head.right = remove_node(head.right,key);

      head.left = remove_node(head.left,key);
    
          
 
    
    Node temp=null, back=null;
    if(head.data >= key)
    {
      if(head.left==null)
      {
        temp=head;
        head=head.right;
      }
      else if(head.right==null)
      {
        temp=head;
        head=head.left;
      }
      else
      {
        temp=head.left;
        back=head;
        while(temp.right!=null)
        {
          back=temp;
          temp=temp.right;
        }
        if(head.left==temp)
        {
          swap_data(head,temp);
          head.left=temp.left;
        }
        else{
          swap_data(head,temp);
          back.right=temp.left;
        }
      }

      temp=null;
      
    }

  }
  return head;
}

  public void delete_keys(int key) {
    if (root != null) {

     
        root = remove_node(root, key);

    } else {
      System.out.print("\n  Empty BST\n");
    }
    System.out.print("\n");

  }

  public static void main(String[] args) {

    BinarySearchTree obj = new BinarySearchTree();
   //Add nodes in binary search tree
    /*
                5
              /   \ 
             /     \
            3       19
           / \     /   \
          2   4   8     31
         /       / \    /
        1       7   15  25   


    */                

    obj.add(5); 
    obj.add(3); 
    obj.add(19); 
    obj.add(2); 
    obj.add(4); 
    obj.add(8); 
    obj.add(31); 
    obj.add(1); 
    obj.add(7); 
    obj.add(25); 
    obj.add(15); 


    obj.inorder(obj.root);

    obj.delete_keys(8);

     /*
      After delete nodes 
      -----------------
                5
              /   \ 
             /     \
            3       7
           / \    
          2   4  
         /           
        1             
    */

    obj.inorder(obj.root);

  }
}

Output

  1   2   3   4   5   7   8  15  19  25  31 
  1   2   3   4   5   7
//C# program
//Delete nodes which are greater than or equal to given value in BST

using System;
//BST node
public class Node {

  public int data;
  public Node left;
  public Node right;

  public Node(int value) {
    data = value;
    left = null;
    right = null;
  }
}
public class BinarySearchTree {


  public Node root;


  public BinarySearchTree() {
    root = null;

  }
  //insert a node in BST
  public void add(int value) {
    //Create a dynamic node of binary search tree 
    Node new_node = new Node(value);

    if (new_node != 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 >= value) {
            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.Write("\nMemory Overflow\n");
    }
  }

  public void inorder(Node head) {
    if (head != null) {

      inorder(head.left);
      Console.Write(head.data + "  ");
      inorder(head.right);
    }
  }

  public void swap_data(Node root1, Node root2) {
    int temp = root2.data;
    root2.data = root1.data;
    root1.data = temp;
  }
  public Node  remove_node(Node head,int key)
  {
    if(head != null)
    {

      head.right = remove_node(head.right,key);

      head.left = remove_node(head.left,key);




      Node temp=null, back=null;
      if(head.data >= key)
      {
        if(head.left==null)
        {
          temp=head;
          head=head.right;
        }
        else if(head.right==null)
        {
          temp=head;
          head=head.left;
        }
        else
        {
          temp=head.left;
          back=head;
          while(temp.right!=null)
          {
            back=temp;
            temp=temp.right;
          }
          if(head.left==temp)
          {
            swap_data(head,temp);
            head.left=temp.left;
          }
          else{
            swap_data(head,temp);
            back.right=temp.left;
          }
        }

        temp=null;

      }

    }
    return head;
  }

  public void delete_keys(int key) {
    if (root != null) {


      root = remove_node(root, key);

    } else {
      Console.Write("\n  Empty BST\n");
    }
    Console.Write("\n");

  }

  public static void Main(String[] args) {

    BinarySearchTree obj = new BinarySearchTree();
    //Add nodes in binary search tree
    /*
                5
              /   \ 
             /     \
            3       19
           / \     /   \
          2   4   8     31
         /       / \    /
        1       7   15  25   


    */                

    obj.add(5); 
    obj.add(3); 
    obj.add(19); 
    obj.add(2); 
    obj.add(4); 
    obj.add(8); 
    obj.add(31); 
    obj.add(1); 
    obj.add(7); 
    obj.add(25); 
    obj.add(15); 


    obj.inorder(obj.root);

    obj.delete_keys(8);

    /*
      After delete nodes 
      -----------------
                5
              /   \ 
             /     \
            3       7
           / \    
          2   4  
         /           
        1             
    */

    obj.inorder(obj.root);

  }
}

Output

  1   2   3   4   5   7   8  15  19  25  31 
  1   2   3   4   5   7
# Python 3 Program
# Delete nodes which are greater than or equal to given value in BST

class Node :

  def __init__(self, value) :
    self.data = value
    self.left = None
    self.right = None
  

class BinarySearchTree :
  
  def __init__(self) :
    self.root = None
  
  def add(self, value) :
    new_node = Node(value)
    if (new_node != None) :
      if (self.root == None) :
        self.root = new_node
      else :
        find = self.root
        while (find != None) :
          if (find.data >= value) :
            if (find.left == None) :
              find.left = new_node
              break
            else :
              find = find.left
            
          else :
            if (find.right == None) :
              find.right = new_node
              break
            else :
              find = find.right
            
          
        
      
    else :
      print("\nMemory Overflow\n")
    
  
  def inorder(self, head) :
    if (head != None) :
      self.inorder(head.left)
      print(head.data ,end="  ")
      self.inorder(head.right)
    
  
  def swap_data(self, root1, root2) :
    temp = root2.data
    root2.data = root1.data
    root1.data = temp
  
  def remove_node(self, head, key) :
    if (head != None) :
      head.right = self.remove_node(head.right, key)
      head.left = self.remove_node(head.left, key)
      temp = None
      back = None
      if (head.data >= key) :
        if (head.left == None) :
          temp = head
          head = head.right
        elif (head.right == None) :
          temp = head
          head = head.left
        else :
          temp = head.left
          back = head
          while (temp.right != None) :
            back = temp
            temp = temp.right
          
          if (head.left == temp) :
            self.swap_data(head, temp)
            head.left = temp.left
          else :
            self.swap_data(head, temp)
            back.right = temp.left
          
        
        temp = None
      
    
    return head
  
  def delete_keys(self, key) :
    if (self.root != None) :
      self.root = self.remove_node(self.root, key)
    else :
      print("\n  Empty BST\n")
    
    print()
  
def main() :
  obj = BinarySearchTree()
  #
  #              5
  #            /   \
  #           /     \
  #          3       19
  #         / \     /  \
  #        2   4   8    31
  #       /       / \    /
  #      1       7   15  25
  #  
  obj.add(5)
  obj.add(3)
  obj.add(19)
  obj.add(2)
  obj.add(4)
  obj.add(8)
  obj.add(31)
  obj.add(1)
  obj.add(7)
  obj.add(25)
  obj.add(15)
  obj.inorder(obj.root)
  obj.delete_keys(8)
    
  #    After delete nodes
  #              5
  #            /   \
  #           /     \
  #          3       7
  #         / \
  #        2   4
  #       /
  #      1
  #  
  obj.inorder(obj.root)
  

if __name__ == "__main__":
  main()

Output

  1   2   3   4   5   7   8  15  19  25  31 
  1   2   3   4   5   7
# Ruby Program
# Delete nodes which are greater than or equal to given value in BST

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 inorder(head) 
    if (head != nil) 
      self.inorder(head.left)
      print(head.data ,"  ")
      self.inorder(head.right)
    end
  end
  def swap_data(root1, root2) 
    temp = root2.data
    root2.data = root1.data
    root1.data = temp
  end
  def remove_node(head, key) 
    if (head != nil) 
      head.right = self.remove_node(head.right, key)
      head.left = self.remove_node(head.left, key)
      temp = nil
      back = nil
      if (head.data >= key) 
        if (head.left == nil) 
          temp = head
          head = head.right
        elsif (head.right == nil) 
          temp = head
          head = head.left
        else 
          temp = head.left
          back = head
          while (temp.right != nil) 
            back = temp
            temp = temp.right
          end
          if (head.left == temp) 
            self.swap_data(head, temp)
            head.left = temp.left
          else 
            self.swap_data(head, temp)
            back.right = temp.left
          end
        end
        temp = nil
      end
    end
    return head
  end
  def delete_keys(key) 
    if (@root != nil) 
      @root = self.remove_node(@root, key)
    else 
      print("\n  Empty BST\n")
    end
    print("\n")
  end
end
def main() 
  obj = BinarySearchTree.new()
  #
  #              5
  #            /   \
  #           /     \
  #          3       19
  #         / \     /  \
  #        2   4   8    31
  #       /       / \    /
  #      1       7   15  25
  #  
  obj.add(5)
  obj.add(3)
  obj.add(19)
  obj.add(2)
  obj.add(4)
  obj.add(8)
  obj.add(31)
  obj.add(1)
  obj.add(7)
  obj.add(25)
  obj.add(15)
  obj.inorder(obj.root)
  obj.delete_keys(8)
    
  #    After delete nodes
  #              5
  #            /   \
  #           /     \
  #          3       7
  #         / \
  #        2   4
  #       /
  #      1
  #  
  obj.inorder(obj.root)
end

main()

Output

  1   2   3   4   5   7   8  15  19  25  31 
  1   2   3   4   5   7
<?php
/*
 Php Program
 Delete nodes which are greater than or equal to given value in BST
*/

class Node {
  public $data;
  public $left;
  public $right;

  function __construct($value) {
    $this->data = $value;
    $this->left = null;
    $this->right = null;
  }
}
class BinarySearchTree {
  public $root;

  function __construct() {
    $this->root = null;
  }
  public  function add($value) {
    $new_node = new Node($value);
    if ($new_node != null) {
      if ($this->root == null) {
        $this->root = $new_node;
      } else {
        $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 {
      echo("\nMemory Overflow\n");
    }
  }
  public  function inorder($head) {
    if ($head != null) {
      $this->inorder($head->left);
      echo($head->data ."  ");
      $this->inorder($head->right);
    }
  }
  public  function swap_data($root1, $root2) {
    $temp = $root2->data;
    $root2->data = $root1->data;
    $root1->data = $temp;
  }
  public  function remove_node($head, $key) {
    if ($head != null) {
      $head->right = $this->remove_node($head->right, $key);
      $head->left = $this->remove_node($head->left, $key);
      $temp = null;
      $back = null;
      if ($head->data >= $key) {
        if ($head->left == null) {
          $temp = $head;
          $head = $head->right;
        } else
        if ($head->right == null) {
          $temp = $head;
          $head = $head->left;
        } else {
          $temp = $head->left;
          $back = $head;
          while ($temp->right != null) {
            $back = $temp;
            $temp = $temp->right;
          }
          if ($head->left == $temp) {
            $this->swap_data($head, $temp);
            $head->left = $temp->left;
          } else {
            $this->swap_data($head, $temp);
            $back->right = $temp->left;
          }
        }
        $temp = null;
      }
    }
    return $head;
  }
  public  function delete_keys($key) {
    if ($this->root != null) {
      $this->root = $this->remove_node($this->root, $key);
    } else {
      echo("\n  Empty BST\n");
    }
    echo("\n");
  }
}
function main() {
  $obj = new BinarySearchTree();
    /*
              5
            /   \ 
           /     \
          3       19
         / \     /  \
        2   4   8    31
       /       / \    /
      1       7   15  25   


  */   
  $obj->add(5);
  $obj->add(3);
  $obj->add(19);
  $obj->add(2);
  $obj->add(4);
  $obj->add(8);
  $obj->add(31);
  $obj->add(1);
  $obj->add(7);
  $obj->add(25);
  $obj->add(15);
  $obj->inorder($obj->root);
  $obj->delete_keys(8);
  /*
    After delete nodes 
    -----------------
              5
            /   \ 
           /     \
          3       7
         / \    
        2   4  
       /           
      1             
  */
  $obj->inorder($obj->root);
}
main();

Output

  1   2   3   4   5   7   8  15  19  25  31 
  1   2   3   4   5   7
/*
 Node Js Program
 Delete nodes which are greater than or equal to given value in BST
*/

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");
    }
  }
  inorder(head) {
    if (head != null) {
      this.inorder(head.left);
      process.stdout.write(head.data + "  ");
      this.inorder(head.right);
    }
  }
  swap_data(root1, root2) {
    var temp = root2.data;
    root2.data = root1.data;
    root1.data = temp;
  }
  remove_node(head, key) {
    if (head != null) {
      head.right = this.remove_node(head.right, key);
      head.left = this.remove_node(head.left, key);
      var temp = null;
      var back = null;
      if (head.data >= key) {
        if (head.left == null) {
          temp = head;
          head = head.right;
        } else
        if (head.right == null) {
          temp = head;
          head = head.left;
        } else {
          temp = head.left;
          back = head;
          while (temp.right != null) {
            back = temp;
            temp = temp.right;
          }
          if (head.left == temp) {
            this.swap_data(head, temp);
            head.left = temp.left;
          } else {
            this.swap_data(head, temp);
            back.right = temp.left;
          }
        }
        temp = null;
      }
    }
    return head;
  }
  delete_keys(key) {
    if (this.root != null) {
      this.root = this.remove_node(this.root, key);
    } else {
      process.stdout.write("\n  Empty BST\n");
    }
    process.stdout.write("\n");
  }
}

function main() {
  var obj = new BinarySearchTree();
    /*
              5
            /   \ 
           /     \
          3       19
         / \     /  \
        2   4   8    31
       /       / \    /
      1       7   15  25   


  */   
  obj.add(5);
  obj.add(3);
  obj.add(19);
  obj.add(2);
  obj.add(4);
  obj.add(8);
  obj.add(31);
  obj.add(1);
  obj.add(7);
  obj.add(25);
  obj.add(15);
  obj.inorder(obj.root);
  obj.delete_keys(8);
  /*
  After delete nodes 
  -----------------
            5
          /   \ 
         /     \
        3       7
       / \    
      2   4  
     /           
    1             
  */
  obj.inorder(obj.root);
}


main();

Output

  1   2   3   4   5   7   8  15  19  25  31 
  1   2   3   4   5   7
/*
 Swift 4 Program
 Delete nodes which are greater than or equal to given value in BST
*/

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 inorder(_ head: Node? ) {
    if (head != nil) {
      self.inorder(head!.left);
      print(head!.data, terminator:"  ");
      self.inorder(head!.right);
    }
  }
  func swap_data(_ root1: Node? , _ root2 : Node? ) {
    let temp: Int = root2!.data;
    root2!.data = root1!.data;
    root1!.data = temp;
  }
  func remove_node(_ element: Node? , _ key : Int) -> Node? {
    var head: Node? = element;
    if (head != nil) {
      head!.right = self.remove_node(head!.right, key);
      head!.left = self.remove_node(head!.left, key);
      var temp: Node? = nil;
      var back: Node? = nil;
      if (head!.data >= key) {
        if (head!.left == nil) {
          temp = head;
          head = head!.right;
        } else
        if (head!.right == nil) {
          temp = head;
          head = head!.left;
        } else {
          temp = head!.left;
          back = head;
          while (temp!.right != nil) {
            back = temp;
            temp = temp!.right;
          }
          if (head!.left === temp) {
            self.swap_data(head, temp);
            head!.left = temp!.left;
          } else {
            self.swap_data(head, temp);
            back!.right = temp!.left;
          }
        }
        temp = nil;
      }
    }
    return head;
  }
  func delete_keys(_ key: Int) {
    if (self.root != nil) {
      self.root = self.remove_node(self.root, key);
    } else {
      print("\n  Empty BST\n");
    }
    print();
  }
}

func main() {
  let obj: BinarySearchTree = BinarySearchTree();
    /*
              5
            /   \ 
           /     \
          3       19
         / \     /  \
        2   4   8    31
       /       / \    /
      1       7   15  25   


  */   
  obj.add(5);
  obj.add(3);
  obj.add(19);
  obj.add(2);
  obj.add(4);
  obj.add(8);
  obj.add(31);
  obj.add(1);
  obj.add(7);
  obj.add(25);
  obj.add(15);
  obj.inorder(obj.root);
  obj.delete_keys(8);
  /*
    After delete nodes 
    -----------------
              5
            /   \ 
           /     \
          3       7
         / \    
        2   4  
       /           
      1             
  */
  obj.inorder(obj.root);
}
main();

Output

  1   2   3   4   5   7   8  15  19  25  31 
  1   2   3   4   5   7

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