Delete a path from given node to root node in BST

Here given code implementation process.
//C Program
//Delete a path from given node to root node 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* delete_path(struct Node*root,int key)
{
if(root != NULL)
{
if(root -> data > key)
{
root->left = delete_path(root->left,key);
}
else if(root->data < key)
{
root->right = delete_path(root->right,key);
}
struct Node*temp=NULL,*back=NULL;
if(root->left==NULL)
{
temp=root;
root=root->right;
}
else if(root->right==NULL)
{
temp=root;
root=root->left;
}
else
{
temp=root->left;
back=temp;
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* find_node(struct Node*root,int key)
{
if(root != NULL)
{
if(root -> data==key)
{
//when leaf node exist
return root;
}
else if(root -> data > key)
{
return find_node(root->left,key);
}
else
{
return find_node(root->right,key);
}
}
return NULL;
}
struct Node* delete_node(struct Node*root,int key)
{
if(root!=NULL)
{
if(find_node(root,key) != NULL)
{
root=delete_path(root,key);
}
else
{
printf("\n Given node %d are not exist\n",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,31);
inorder(root);
return 0;
}
Output
1 2 3 4 5 7 8 15 19 25 31
1 2 3 4 7 8 15 25
/*
C++ Program
Delete a path from given node to root node 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 *delete_nodes(Node *head, int key) {
if (head != NULL) {
if (head->data > key) {
head->left = this->delete_nodes(head->left, key);
} else {
head->right = this->delete_nodes(head->right, key);
}
Node *temp = NULL, *back = NULL;
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;
}
Node *find_node(Node *head, int key) {
if (head != NULL) {
if (head->data == key) {
return head;
} else
if (head->data > key) {
return this->find_node(head->left, key);
} else {
return this->find_node(head->right, key);
}
}
return NULL;
}
void delete_path(int key) {
if (this->root != NULL) {
if (this->find_node(this->root, key) != NULL) {
this->root = this->delete_nodes(this->root, key);
} else {
cout << "\n Given leaf node " << key << " are not exist\n";
}
} 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_path(31);
/*
After delete path
-----------------
4
/ \
/ \
3 15
/ / \
2 8 25
/ /
1 7
*/
obj.inorder(obj.root);
return 0;
}
Output
1 2 3 4 5 7 8 15 19 25 31
1 2 3 4 7 8 15 25
//Java program
//Delete a path from given node to root node 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 delete_nodes(Node head, int key) {
if (head != null) {
if (head.data > key) {
head.left = delete_nodes(head.left, key);
} else {
head.right = delete_nodes(head.right, key);
}
Node temp = null, back = null;
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 Node find_node(Node head, int key) {
if (head != null) {
if (head.data == key) {
//when leaf node exist
return head;
} else if (head.data > key) {
return find_node(head.left, key);
} else {
return find_node(head.right, key);
}
}
return null;
}
public void delete_path(int key) {
if (root != null) {
if (find_node(root, key) != null) {
root = delete_nodes(root, key);
} else {
System.out.print("\n Given leaf node " + key + " are not exist\n");
}
} 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_path(31);
/*
After delete path
-----------------
4
/ \
/ \
3 15
/ / \
2 8 25
/ /
1 7
*/
obj.inorder(obj.root);
}
}
Output
1 2 3 4 5 7 8 15 19 25 31
1 2 3 4 7 8 15 25
//C# program
//Delete a path from given node to root node 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 delete_nodes(Node head, int key) {
if (head != null) {
if (head.data > key) {
head.left = delete_nodes(head.left, key);
} else {
head.right = delete_nodes(head.right, key);
}
Node temp = null, back = null;
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 Node find_node(Node head, int key) {
if (head != null) {
if (head.data == key) {
//when leaf node exist
return head;
} else if (head.data > key) {
return find_node(head.left, key);
} else {
return find_node(head.right, key);
}
}
return null;
}
public void delete_path(int key) {
if (root != null) {
if (find_node(root, key) != null) {
root = delete_nodes(root, key);
} else {
Console.Write("\n Given leaf node " + key + " are not exist\n");
}
} 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_path(31);
/*
After delete path
-----------------
4
/ \
/ \
3 15
/ / \
2 8 25
/ /
1 7
*/
obj.inorder(obj.root);
}
}
Output
1 2 3 4 5 7 8 15 19 25 31
1 2 3 4 7 8 15 25
# Python 3 Program
# Delete a path from given node to root node 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 delete_nodes(self, head, key) :
if (head != None) :
if (head.data > key) :
head.left = self.delete_nodes(head.left, key)
else :
head.right = self.delete_nodes(head.right, key)
temp = None
back = None
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 find_node(self, head, key) :
if (head != None) :
if (head.data == key) :
return head
elif (head.data > key) :
return self.find_node(head.left, key)
else :
return self.find_node(head.right, key)
return None
def delete_path(self, key) :
if (self.root != None) :
if (self.find_node(self.root, key) != None) :
self.root = self.delete_nodes(self.root, key)
else :
print("\n Given leaf node ", key ," are not exist\n")
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_path(31)
#
# After delete path
# 4
# / \
# / \
# 3 15
# / / \
# 2 8 25
# / /
# 1 7
#
obj.inorder(obj.root)
if __name__ == "__main__":
main()
Output
1 2 3 4 5 7 8 15 19 25 31
1 2 3 4 7 8 15 25
# Ruby Program
# Delete a path from given node to root node 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 delete_nodes(head, key)
if (head != nil)
if (head.data > key)
head.left = self.delete_nodes(head.left, key)
else
head.right = self.delete_nodes(head.right, key)
end
temp = nil
back = nil
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
return head
end
def find_node(head, key)
if (head != nil)
if (head.data == key)
return head
elsif (head.data > key)
return self.find_node(head.left, key)
else
return self.find_node(head.right, key)
end
end
return nil
end
def delete_path(key)
if (@root != nil)
if (self.find_node(@root, key) != nil)
@root = self.delete_nodes(@root, key)
else
print("\n Given leaf node ", key ," are not exist\n")
end
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_path(31)
#
# After delete path
# 4
# / \
# / \
# 3 15
# / / \
# 2 8 25
# / /
# 1 7
#
obj.inorder(obj.root)
end
main()
Output
1 2 3 4 5 7 8 15 19 25 31
1 2 3 4 7 8 15 25
<?php
/*
Php Program
Delete a path from given node to root node 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 delete_nodes($head, $key) {
if ($head != null) {
if ($head->data > $key) {
$head->left = $this->delete_nodes($head->left, $key);
} else {
$head->right = $this->delete_nodes($head->right, $key);
}
$temp = null;
$back = null;
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 find_node($head, $key) {
if ($head != null) {
if ($head->data == $key) {
return $head;
} else
if ($head->data > $key) {
return $this->find_node($head->left, $key);
} else {
return $this->find_node($head->right, $key);
}
}
return null;
}
public function delete_path($key) {
if ($this->root != null) {
if ($this->find_node($this->root, $key) != null) {
$this->root = $this->delete_nodes($this->root, $key);
} else {
echo("\n Given leaf node ". $key ." are not exist\n");
}
} 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_path(31);
/*
After delete path
-----------------
4
/ \
/ \
3 15
/ / \
2 8 25
/ /
1 7
*/
$obj->inorder($obj->root);
}
main();
Output
1 2 3 4 5 7 8 15 19 25 31
1 2 3 4 7 8 15 25
/*
Node Js Program
Delete a path from given node to root node 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;
}
delete_nodes(head, key) {
if (head != null) {
if (head.data > key) {
head.left = this.delete_nodes(head.left, key);
} else {
head.right = this.delete_nodes(head.right, key);
}
var temp = null;
var back = null;
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;
}
find_node(head, key) {
if (head != null) {
if (head.data == key) {
return head;
} else
if (head.data > key) {
return this.find_node(head.left, key);
} else {
return this.find_node(head.right, key);
}
}
return null;
}
delete_path(key) {
if (this.root != null) {
if (this.find_node(this.root, key) != null) {
this.root = this.delete_nodes(this.root, key);
} else {
process.stdout.write("\n Given leaf node " + key + " are not exist\n");
}
} 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_path(31);
/*
After delete path
-----------------
4
/ \
/ \
3 15
/ / \
2 8 25
/ /
1 7
*/
obj.inorder(obj.root);
}
main();
Output
1 2 3 4 5 7 8 15 19 25 31
1 2 3 4 7 8 15 25
/*
Swift 4 Program
Delete a path from given node to root node 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 delete_nodes(_ nodeSet: Node? , _ key : Int) -> Node? {
var head: Node? = nodeSet;
if (nodeSet != nil) {
if (nodeSet!.data > key) {
nodeSet!.left = self.delete_nodes(nodeSet!.left, key);
} else {
nodeSet!.right = self.delete_nodes(nodeSet!.right, key);
}
var temp: Node? = nil;
var back: Node? = nil;
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 find_node(_ head: Node? , _ key : Int) -> Node? {
if (head != nil) {
if (head!.data == key) {
return head;
} else
if (head!.data > key) {
return self.find_node(head!.left, key);
} else {
return self.find_node(head!.right, key);
}
}
return nil;
}
func delete_path(_ key: Int) {
if (self.root != nil) {
if (self.find_node(self.root, key) != nil) {
self.root = self.delete_nodes(self.root, key);
} else {
print("\n Given leaf node ", key ," are not exist\n");
}
} else {
print("\n Empty BST\n");
}
print("\n");
}
}
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_path(31);
/*
After delete path
-----------------
4
/ \
/ \
3 15
/ / \
2 8 25
/ /
1 7
*/
obj.inorder(obj.root);
}
main();
Output
1 2 3 4 5 7 8 15 19 25 31
1 2 3 4 7 8 15 25
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