Delete sorted sequence in Binary Search Tree

Here given code implementation process.
//C Program
//Delete sorted sequence 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
}
}
int binary_search(int *arr,int size,int element)
{
if(size <= 1) return -1;
int i=0, j = (size-1),mid=0;
//base condition
while(j > i && arr[i] != element && arr[j] != element)
{
//Get middle element
mid = (i+j)/2;
if(arr[mid] > element)
{
//When middle element of index i and j are greater
j = mid-1;
}
else if(arr[mid] < element)
{
//When middle element of index i and j are less
i = mid+1;
}
else
{
//when get element
i = mid;
break;
}
}
if(arr[i] == element )
{
return i;
}
else if(arr[j] == element )
{
return j;
}
return -1;
}
//Swap two nodes values
void swap_data(struct Node*root1, struct Node*root2)
{
int temp=root1->data;
root1->data=root2->data;
root2->data=temp;
}
struct Node* delete_elements(struct Node*root,
struct Node*left_side,
struct Node*right_side,
int collection[],
int size
)
{
if(root != NULL)
{
root->left = delete_elements(root->left,left_side,root,collection,size);
root->right = delete_elements(root->right,root,right_side,collection,size);
if(binary_search(collection,size,root->data)!=-1)
{
if(root->left == NULL && root->right == NULL )
{
//Delete leaf node
free(root);
root=NULL;
}
else if(root->left == NULL)
{
right_side=root->right;
free(root);
root=right_side;
}
else if(root->right==NULL)
{
left_side=root->left;
free(root);
root=left_side;
}
}
else if(left_side != NULL && binary_search(collection,size,left_side->data)!=-1)
{
//Swap element values
swap_data(left_side,root);
right_side=root->right;
free(root);
root=right_side;
}
else if(right_side != NULL && binary_search(collection,size,right_side->data)!=-1)
{
//swap element values
swap_data(right_side,root);
left_side=root->left;
free(root);
root=left_side;
}
}
return root;
}
struct Node* delete_collection(struct Node*root,
int collection[],
int size)
{
if(root != NULL)
{
return delete_elements(root,NULL,NULL,collection,size);
}
else
{
printf("Empty BST\n");
return NULL;
}
}
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
/*
5
/ \
3 9
/ \ / \
1 4 8 11
/ \ / \
-3 2 7 12
*/
add(&root,5);
add(&root,3);
add(&root,9);
add(&root,1);
add(&root,4);
add(&root,8);
add(&root,11);
add(&root,-3);
add(&root,2);
add(&root,7);
add(&root,12);
preorder(root);//Before Delete
int sort_collection[]={1,5,7,9,12};
int size = sizeof(sort_collection)/sizeof(sort_collection[0]);
root=delete_collection(root,sort_collection,size);
printf("\n");
preorder(root);//After Delete
return 0;
}
Output
5 3 1 -3 2 4 9 8 7 11 12
4 3 -3 2 8 11
/*
C++ Program
Delete sorted sequence in Binary Search Tree
*/
#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 preorder(Node *head) {
if (head != NULL) {
cout << head->data << " ";
this->preorder(head->left);
this->preorder(head->right);
}
}
void swap_data(Node *root1, Node *root2) {
int temp = root2->data;
root2->data = root1->data;
root1->data = temp;
}
int binary_search(int arr[], int size, int element) {
int i = 0, j = size - 1, mid = 0;
while (j > 0 && j > i && arr[i] != element && arr[j] != element) {
mid = (i + j) / 2;
if (arr[mid] > element) {
j = mid - 1;
} else
if (arr[mid] < element) {
i = mid + 1;
} else {
i = mid;
break;;
}
}
if (i != -1 && arr[i] == element) {
return i;
} else
if (j != -1 && arr[j] == element) {
return j;
}
return -1;
}
Node *delete_elements(Node *head, Node *left_side, Node *right_side, int collection[], int size) {
if (head != NULL) {
head->left = this->delete_elements(head->left, left_side, head, collection, size);
head->right = this->delete_elements(head->right, head, right_side, collection, size);
if (this->binary_search(collection, size, head->data) != -1) {
if (head->left == NULL && head->right == NULL) {
head = NULL;
} else
if (head->left == NULL) {
right_side = head->right;
head = right_side;
} else
if (head->right == NULL) {
left_side = head->left;
head = left_side;
}
} else
if (left_side != NULL && this->binary_search(collection, size, left_side->data) != -1) {
this->swap_data(left_side, head);
right_side = head->right;
head = right_side;
} else
if (right_side != NULL && this->binary_search(collection, size, right_side->data) != -1) {
this->swap_data(right_side, head);
left_side = head->left;
head = left_side;
}
}
return head;
}
void delete_collection(int collection[], int size) {
if (this->root != NULL) {
this->root = this->delete_elements(this->root, NULL, NULL, collection, size);
} else {
cout << "Empty BST\n";
}
}
};
int main() {
BinarySearchTree obj ;
//Add nodes in binary search tree
/*
5
/ \
3 9
/ \ / \
1 4 8 11
/ \ / \
-3 2 7 12
*/
obj.add(5);
obj.add(3);
obj.add(9);
obj.add(1);
obj.add(4);
obj.add(8);
obj.add(11);
obj.add(-3);
obj.add(2);
obj.add(7);
obj.add(12);
obj.preorder(obj.root);
int sort_collection[] = { 1, 5, 7, 9, 12 };
int size = sizeof(sort_collection)/sizeof(sort_collection[0]);
obj.delete_collection(sort_collection, size);
cout << "\n";
obj.preorder(obj.root);
return 0;
}
Output
5 3 1 -3 2 4 9 8 7 11 12
4 3 -3 2 8 11
//Java program
//Delete sorted sequence in Binary search tree
//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 preorder(Node head) {
if (head != null) {
System.out.print(head.data + " ");
preorder(head.left);
preorder(head.right);
}
}
public void swap_data(Node root1, Node root2) {
int temp = root2.data;
root2.data = root1.data;
root1.data = temp;
}
//Method which is finding given element index
public int binary_search(int[] arr, int size, int element) {
int i = 0, j = size - 1, mid = 0;
//base condition
while (j > 0 && j > i && arr[i] != element && arr[j] != element) {
//Get middle element
mid = (i + j) / 2;
if (arr[mid] > element) {
//When middle element of index i and j are greater
j = mid - 1;
} else if (arr[mid] < element) {
//When middle element of index i and j are less
i = mid + 1;
} else {
//when get element
i = mid;
break;
}
}
if (i != -1 && arr[i] == element) {
return i;
} else if (j != -1 && arr[j] == element) {
return j;
}
return -1;
}
public Node delete_elements(Node head,
Node left_side,
Node right_side,
int[] collection,
int size
) {
if (head != null) {
head.left = delete_elements(head.left, left_side, head, collection, size);
head.right = delete_elements(head.right, head, right_side, collection, size);
if (binary_search(collection, size, head.data) != -1) {
if (head.left == null && head.right == null) {
//Delete leaf node
head = null;
} else if (head.left == null) {
right_side = head.right;
head = right_side;
} else if (head.right == null) {
left_side = head.left;
head = left_side;
}
} else if (left_side != null && binary_search(collection, size, left_side.data) != -1) {
//Swap element values
swap_data(left_side, head);
right_side = head.right;
head = right_side;
} else if (right_side != null && binary_search(collection, size, right_side.data) != -1) {
//swap element values
swap_data(right_side, head);
left_side = head.left;
head = left_side;
}
}
return head;
}
public void delete_collection(int collection[],
int size) {
if (root != null) {
root = delete_elements(root, null, null, collection, size);
} else {
System.out.print("Empty BST\n");
}
}
public static void main(String[] args) {
BinarySearchTree obj = new BinarySearchTree();
//Add nodes in binary search tree
/*
5
/ \
3 9
/ \ / \
1 4 8 11
/ \ / \
-3 2 7 12
*/
obj.add(5);
obj.add(3);
obj.add(9);
obj.add(1);
obj.add(4);
obj.add(8);
obj.add(11);
obj.add(-3);
obj.add(2);
obj.add(7);
obj.add(12);
obj.preorder(obj.root); //Before Delete
int[] sort_collection = { 1, 5, 7, 9, 12 };
int size = sort_collection.length;
obj.delete_collection(sort_collection, size);
System.out.print("\n");
obj.preorder(obj.root); //After Delete
}
}
Output
5 3 1 -3 2 4 9 8 7 11 12
4 3 -3 2 8 11
//C# program
//Delete sorted sequence in Binary search tree
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 preorder(Node head) {
if (head != null) {
Console.Write(head.data + " ");
preorder(head.left);
preorder(head.right);
}
}
public void swap_data(Node root1, Node root2) {
int temp = root2.data;
root2.data = root1.data;
root1.data = temp;
}
//Method which is finding given element index
public int binary_search(int[] arr, int size, int element) {
int i = 0, j = size - 1, mid = 0;
//base condition
while (j > 0 && j > i && arr[i] != element && arr[j] != element) {
//Get middle element
mid = (i + j) / 2;
if (arr[mid] > element) {
//When middle element of index i and j are greater
j = mid - 1;
} else if (arr[mid] < element) {
//When middle element of index i and j are less
i = mid + 1;
} else {
//when get element
i = mid;
break;
}
}
if (i != -1 && arr[i] == element) {
return i;
} else if (j != -1 && arr[j] == element) {
return j;
}
return -1;
}
public Node delete_elements(Node head,
Node left_side,
Node right_side,
int[] collection,
int size
) {
if (head != null) {
head.left = delete_elements(head.left, left_side, head, collection, size);
head.right = delete_elements(head.right, head, right_side, collection, size);
if (binary_search(collection, size, head.data) != -1) {
if (head.left == null && head.right == null) {
//Delete leaf node
head = null;
} else if (head.left == null) {
right_side = head.right;
head = right_side;
} else if (head.right == null) {
left_side = head.left;
head = left_side;
}
} else if (left_side != null && binary_search(collection, size, left_side.data) != -1) {
//Swap element values
swap_data(left_side, head);
right_side = head.right;
head = right_side;
} else if (right_side != null && binary_search(collection, size, right_side.data) != -1) {
//swap element values
swap_data(right_side, head);
left_side = head.left;
head = left_side;
}
}
return head;
}
public void delete_collection(int []collection,
int size) {
if (root != null) {
root = delete_elements(root, null, null, collection, size);
} else {
Console.Write("Empty BST\n");
}
}
public static void Main(String[] args) {
BinarySearchTree obj = new BinarySearchTree();
//Add nodes in binary search tree
/*
5
/ \
3 9
/ \ / \
1 4 8 11
/ \ / \
-3 2 7 12
*/
obj.add(5);
obj.add(3);
obj.add(9);
obj.add(1);
obj.add(4);
obj.add(8);
obj.add(11);
obj.add(-3);
obj.add(2);
obj.add(7);
obj.add(12);
obj.preorder(obj.root); //Before Delete
int[] sort_collection = { 1, 5, 7, 9, 12 };
int size = sort_collection.Length;
obj.delete_collection(sort_collection, size);
Console.Write("\n");
obj.preorder(obj.root); //After Delete
}
}
Output
5 3 1 -3 2 4 9 8 7 11 12
4 3 -3 2 8 11
# Python 3 Program
# Delete sorted sequence in Binary Search Tree
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 preorder(self, head) :
if (head != None) :
print(head.data ,end=" ")
self.preorder(head.left)
self.preorder(head.right)
def swap_data(self, root1, root2) :
temp = root2.data
root2.data = root1.data
root1.data = temp
def binary_search(self, arr, size, element) :
i = 0
j = size - 1
mid = 0
while (j > 0 and j > i and arr[i] != element and arr[j] != element) :
mid = int((i + j) / 2)
if (arr[mid] > element) :
j = mid - 1
elif (arr[mid] < element) :
i = mid + 1
else :
i = mid
break
if (i != -1 and arr[i] == element) :
return i
elif (j != -1 and arr[j] == element) :
return j
return -1
def delete_elements(self, head, left_side, right_side, collection, size) :
if (head != None) :
head.left = self.delete_elements(head.left, left_side, head, collection, size)
head.right = self.delete_elements(head.right, head, right_side, collection, size)
if (self.binary_search(collection, size, head.data) != -1) :
if (head.left == None and head.right == None) :
head = None
elif (head.left == None) :
right_side = head.right
head = right_side
elif (head.right == None) :
left_side = head.left
head = left_side
elif (left_side != None and self.binary_search(collection, size, left_side.data) != -1) :
self.swap_data(left_side, head)
right_side = head.right
head = right_side
elif (right_side != None and self.binary_search(collection, size, right_side.data) != -1) :
self.swap_data(right_side, head)
left_side = head.left
head = left_side
return head
def delete_collection(self, collection, size) :
if (self.root != None) :
self.root = self.delete_elements(self.root, None, None, collection, size)
else :
print("Empty BST\n")
def main() :
obj = BinarySearchTree()
#
# 5
# / \
# 3 9
# / \ / \
# 1 4 8 11
# / \ / \
# -3 2 7 12
#
obj.add(5)
obj.add(3)
obj.add(9)
obj.add(1)
obj.add(4)
obj.add(8)
obj.add(11)
obj.add(-3)
obj.add(2)
obj.add(7)
obj.add(12)
obj.preorder(obj.root)
sort_collection = [1, 5, 7, 9, 12]
size = len(sort_collection)
obj.delete_collection(sort_collection, size)
print()
obj.preorder(obj.root)
if __name__ == "__main__":
main()
Output
5 3 1 -3 2 4 9 8 7 11 12
4 3 -3 2 8 11
# Ruby Program
# Delete sorted sequence 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 preorder(head)
if (head != nil)
print(head.data ," ")
self.preorder(head.left)
self.preorder(head.right)
end
end
def swap_data(root1, root2)
temp = root2.data
root2.data = root1.data
root1.data = temp
end
def binary_search(arr, size, element)
i = 0
j = size - 1
mid = 0
while (j > 0 and j > i and arr[i] != element and arr[j] != element)
mid = (i + j) / 2
if (arr[mid] > element)
j = mid - 1
elsif (arr[mid] < element)
i = mid + 1
else
i = mid
break
end
end
if (i != -1 and arr[i] == element)
return i
elsif (j != -1 and arr[j] == element)
return j
end
return -1
end
def delete_elements(head, left_side, right_side, collection, size)
if (head != nil)
head.left = self.delete_elements(head.left, left_side, head, collection, size)
head.right = self.delete_elements(head.right, head, right_side, collection, size)
if (self.binary_search(collection, size, head.data) != -1)
if (head.left == nil and head.right == nil)
head = nil
elsif (head.left == nil)
right_side = head.right
head = right_side
elsif (head.right == nil)
left_side = head.left
head = left_side
end
elsif (left_side != nil and self.binary_search(collection, size, left_side.data) != -1)
self.swap_data(left_side, head)
right_side = head.right
head = right_side
elsif (right_side != nil and self.binary_search(collection, size, right_side.data) != -1)
self.swap_data(right_side, head)
left_side = head.left
head = left_side
end
end
return head
end
def delete_collection(collection, size)
if (@root != nil)
@root = self.delete_elements(@root, nil, nil, collection, size)
else
print("Empty BST\n")
end
end
end
def main()
obj = BinarySearchTree.new()
#
# 5
# / \
# 3 9
# / \ / \
# 1 4 8 11
# / \ / \
# -3 2 7 12
#
obj.add(5)
obj.add(3)
obj.add(9)
obj.add(1)
obj.add(4)
obj.add(8)
obj.add(11)
obj.add(-3)
obj.add(2)
obj.add(7)
obj.add(12)
obj.preorder(obj.root)
sort_collection = [1, 5, 7, 9, 12]
size = sort_collection.length
obj.delete_collection(sort_collection, size)
print("\n")
obj.preorder(obj.root)
end
main()
Output
5 3 1 -3 2 4 9 8 7 11 12
4 3 -3 2 8 11
<?php
/*
Php Program
Delete sorted sequence in Binary Search Tree
*/
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 preorder($head) {
if ($head != null) {
echo($head->data ." ");
$this->preorder($head->left);
$this->preorder($head->right);
}
}
public function swap_data($root1, $root2) {
$temp = $root2->data;
$root2->data = $root1->data;
$root1->data = $temp;
}
public function binary_search($arr, $size, $element) {
$i = 0;
$j = $size - 1;
$mid = 0;
while ($j > 0 && $j > $i && $arr[$i] != $element && $arr[$j] != $element) {
$mid = intval(($i + $j) / 2);
if ($arr[$mid] > $element) {
$j = $mid - 1;
} else if ($arr[$mid] < $element) {
$i = $mid + 1;
} else {
$i = $mid;
break;
}
}
if ($i != -1 && $arr[$i] == $element) {
return $i;
}
else if ($j != -1 && $arr[$j] == $element) {
return $j;
}
return -1;
}
public function delete_elements($head, $left_side, $right_side, $collection, $size) {
if ($head != null) {
$head->left = $this->delete_elements($head->left, $left_side, $head, $collection, $size);
$head->right = $this->delete_elements($head->right, $head, $right_side, $collection, $size);
if ($this->binary_search($collection, $size, $head->data) != -1) {
if ($head->left == null && $head->right == null) {
$head = null;
} else
if ($head->left == null) {
$right_side = $head->right;
$head = $right_side;
} else
if ($head->right == null) {
$left_side = $head->left;
$head = $left_side;
}
} else
if ($left_side != null && $this->binary_search($collection, $size, $left_side->data) != -1) {
$this->swap_data($left_side, $head);
$right_side = $head->right;
$head = $right_side;
} else
if ($right_side != null && $this->binary_search($collection, $size, $right_side->data) != -1) {
$this->swap_data($right_side, $head);
$left_side = $head->left;
$head = $left_side;
}
}
return $head;
}
public function delete_collection($collection, $size) {
if ($this->root != null) {
$this->root = $this->delete_elements($this->root, null, null, $collection, $size);
} else {
echo ("Empty BST\n");
}
}
}
function main() {
$obj = new BinarySearchTree();
//Binary search tree
/*
5
/ \
3 9
/ \ / \
1 4 8 11
/ \ / \
-3 2 7 12
*/
$obj->add(5);
$obj->add(3);
$obj->add(9);
$obj->add(1);
$obj->add(4);
$obj->add(8);
$obj->add(11);
$obj->add(-3);
$obj->add(2);
$obj->add(7);
$obj->add(12);
$obj->preorder($obj->root);
$sort_collection = array(1, 5, 7, 9, 12);
$size = count($sort_collection);
$obj->delete_collection($sort_collection, $size);
echo ("\n");
$obj->preorder($obj->root);
}
main();
Output
5 3 1 -3 2 4 9 8 7 11 12
4 3 -3 2 8 11
/*
Node Js Program
Delete sorted sequence 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");
}
}
preorder(head) {
if (head != null) {
process.stdout.write(head.data + " ");
this.preorder(head.left);
this.preorder(head.right);
}
}
swap_data(root1, root2) {
var temp = root2.data;
root2.data = root1.data;
root1.data = temp;
}
binary_search(arr, size, element) {
var i = 0;
var j = size - 1;
var mid = 0;
while (j > 0 && j > i && arr[i] != element && arr[j] != element) {
mid = (i + j) / 2;
if (arr[mid] > element) {
j = mid - 1;
} else
if (arr[mid] < element) {
i = mid + 1;
} else {
i = mid;
break;;
}
}
if (i != -1 && arr[i] == element) {
return i;
} else
if (j != -1 && arr[j] == element) {
return j;
}
return -1;
}
delete_elements(head, left_side, right_side, collection, size) {
if (head != null) {
head.left = this.delete_elements(head.left, left_side, head, collection, size);
head.right = this.delete_elements(head.right, head, right_side, collection, size);
if (this.binary_search(collection, size, head.data) != -1) {
if (head.left == null && head.right == null) {
head = null;
} else
if (head.left == null) {
right_side = head.right;
head = right_side;
} else
if (head.right == null) {
left_side = head.left;
head = left_side;
}
} else
if (left_side != null && this.binary_search(collection, size, left_side.data) != -1) {
this.swap_data(left_side, head);
right_side = head.right;
head = right_side;
} else
if (right_side != null && this.binary_search(collection, size, right_side.data) != -1) {
this.swap_data(right_side, head);
left_side = head.left;
head = left_side;
}
}
return head;
}
delete_collection(collection, size) {
if (this.root != null) {
this.root = this.delete_elements(this.root, null, null, collection, size);
} else {
process.stdout.write("Empty BST\n");
}
}
}
function main() {
var obj = new BinarySearchTree();
//Binary search tree
/*
5
/ \
3 9
/ \ / \
1 4 8 11
/ \ / \
-3 2 7 12
*/
obj.add(5);
obj.add(3);
obj.add(9);
obj.add(1);
obj.add(4);
obj.add(8);
obj.add(11);
obj.add(-3);
obj.add(2);
obj.add(7);
obj.add(12);
obj.preorder(obj.root);
var sort_collection = [1, 5, 7, 9, 12];
var size = sort_collection.length;
obj.delete_collection(sort_collection, size);
process.stdout.write("\n");
obj.preorder(obj.root);
}
main();
Output
5 3 1 -3 2 4 9 8 7 11 12
4 3 -3 2 8 11
/*
Swift 4 Program
Delete sorted sequence 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 preorder(_ head: Node? ) {
if (head != nil) {
print(head!.data ,terminator:" ");
self.preorder(head!.left);
self.preorder(head!.right);
}
}
func swap_data(_ root1: Node? , _ root2 : Node? ) {
let temp: Int = root2!.data;
root2!.data = root1!.data;
root1!.data = temp;
}
func binary_search(_ arr: [Int] , _ size : Int, _ element: Int) -> Int {
var i: Int = 0;
var j = size - 1;
var mid = 0;
while (j > 0 && j > i && arr[i] != element && arr[j] != element) {
mid = ((i + j) / 2);
if (arr[mid] > element) {
j = mid - 1;
} else
if (arr[mid] < element) {
i = mid + 1;
} else {
i = mid;
break;
}
}
if (i != -1 && arr[i] == element) {
return i;
} else
if (j != -1 && arr[j] == element) {
return j;
}
return -1;
}
func delete_elements(_ element: Node? , _ left_s : Node? , _ right_s : Node? , _ collection : [Int] , _ size : Int) -> Node? {
var head : Node? = element;
var left_side : Node? = left_s;
var right_side : Node? = right_s;
if (head != nil) {
head!.left = self.delete_elements(head!.left, left_side, head, collection, size);
head!.right = self.delete_elements(head!.right, head, right_side, collection, size);
if (self.binary_search(collection, size, head!.data) != -1) {
if (head!.left == nil && head!.right == nil) {
head = nil;
} else
if (head!.left == nil) {
right_side = head!.right;
head = right_side;
} else
if (head!.right == nil) {
left_side = head!.left;
head = left_side;
}
} else
if (left_side != nil && self.binary_search(collection, size, left_side!.data) != -1) {
self.swap_data(left_side, head);
right_side = head!.right;
head = right_side;
} else
if (right_side != nil && self.binary_search(collection, size, right_side!.data) != -1) {
self.swap_data(right_side, head);
left_side = head!.left;
head = left_side;
}
}
return head;
}
func delete_collection(_ collection: [Int], _ size: Int) {
if (self.root != nil) {
self.root = self.delete_elements(self.root, nil, nil, collection, size);
} else {
print("Empty BST\n");
}
}
}
func main() {
let obj: BinarySearchTree = BinarySearchTree();
//Binary search tree
/*
5
/ \
3 9
/ \ / \
1 4 8 11
/ \ / \
-3 2 7 12
*/
obj.add(5);
obj.add(3);
obj.add(9);
obj.add(1);
obj.add(4);
obj.add(8);
obj.add(11);
obj.add(-3);
obj.add(2);
obj.add(7);
obj.add(12);
obj.preorder(obj.root);
let sort_collection: [Int] = [1, 5, 7, 9, 12];
let size: Int = sort_collection.count;
obj.delete_collection(sort_collection, size);
print();
obj.preorder(obj.root);
}
main();
Output
5 3 1 -3 2 4 9 8 7 11 12
4 3 -3 2 8 11
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