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
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