Binary Tree to Binary Search Tree Conversion
Here given code implementation process.
//C Program
//Binary Tree to Binary Search Tree Conversion
#include<stdio.h>
#include<stdlib.h>
//structure of Binary Search Tree node
struct Node
{
int data;
struct Node *left, *right;
};
struct Node *insert(int data)
{
//create dynamic memory to new binary tree node
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
}
else
{
printf("Memory Overflow\n");
exit(0); //Terminate program execution
}
//return reference
return new_node;
}
void preorder(struct Node *root)
{
if (root != NULL)
{
printf(" %d", root->data);
preorder(root->left);
preorder(root->right);
}
}
//Get the existing Binary search tree nodes
void get_element(struct Node *root, int auxiliary[], int *index)
{
if (root != NULL)
{
//add element into array
auxiliary[( *index) ++] = root->data;
get_element(root->left, auxiliary, index);
get_element(root->right, auxiliary, index);
}
}
int element_size(struct Node *root)
{
if (root != NULL)
{
return element_size(root->left) + element_size(root->right) + 1;
}
return 0;
}
//Swap two nodes in array
void swap(int data[], int start, int end)
{
int back_up = data[start];
data[start] = data[end];
data[end] = back_up;
}
int pivit(int start, int data[], int end)
{
int temp = start - 1;
for (int i = start; i < end; ++i)
{
if (data[i] < data[end])
{
//swap data
swap(data, ++temp, i);
}
}
swap(data, temp + 1, end);
return temp + 1;
}
//Sort the array element using quick sort
void quick_sort(int start, int end, int *data)
{
if (start < end)
{
int pv = pivit(start, data, end);
quick_sort(start, pv - 1, data);
quick_sort(pv + 1, end, data);
}
}
void replace(struct Node *root, int *auxiliary, int *index)
{
if (root != NULL)
{
replace(root->left, auxiliary, index);
root->data = auxiliary[( *index) ++];
replace(root->right, auxiliary, index);
}
}
void bst(struct Node *root)
{
int size = element_size(root);
//Create an array which are store the BT elements
int auxiliary[size];
int index = 0;
//Get all array elements
get_element(root, auxiliary, & index);
//sort element
quick_sort(0, size - 1, auxiliary);
index = 0;
//Change sort element
replace(root, auxiliary, & index);
}
int main()
{
struct Node *root = NULL;
/* Make A Binary Tree
-----------------------
1
/ \
2 3
/ \ / \
4 5 6 7
/ \
8 9
*/
//insertion of binary Tree nodes
root = insert(1);
root->left = insert(2);
root->left->right = insert(5);
root->left->right->left = insert(8);
root->right = insert(3);
root->right->right = insert(7);
root->right->left = insert(6);
root->right->left->right = insert(9);
root->left->left = insert(4);
printf(" Preorder \n");
preorder(root);
bst(root);
printf("\n After Convert BT to BST");
printf("\n Preorder \n");
preorder(root);
return 0;
}
Output
Preorder
1 2 4 5 8 3 6 9 7
After Convert BT to BST
Preorder
5 2 1 4 3 8 6 7 9
/*
Java Program
Binary Tree to Binary Search Tree Conversion
*/
//Tree node
class Node
{
public int data;
public Node left;
public Node right;
public Node(int data)
{
//Set data value of binary tree node
this.data = data;
this.left = null;
this.right = null;
}
}
class BinarySearchTree
{
public Node root;
public int location;
public BinarySearchTree()
{
root = null;
location = 0;
}
public void preorder(Node root)
{
if (root != null)
{
System.out.print(" " + root.data);
preorder(root.left);
preorder(root.right);
}
}
//Get the existing Binary search tree nodes
public void get_element(Node root, int[] auxiliary)
{
if (root != null)
{
//add element into array
auxiliary[this.location] = root.data;
this.location += 1;
get_element(root.left, auxiliary);
get_element(root.right, auxiliary);
}
}
public int element_size(Node root)
{
if (root != null)
{
return element_size(root.left) + element_size(root.right) + 1;
}
return 0;
}
//Swap two nodes in array
public void swap(int[] data, int start, int end)
{
int back_up = data[start];
data[start] = data[end];
data[end] = back_up;
}
public int pivit(int start, int[] data, int end)
{
int temp = start - 1;
for (int i = start; i < end; ++i)
{
if (data[i] < data[end])
{
//swap data
swap(data, ++temp, i);
}
}
swap(data, temp + 1, end);
return temp + 1;
}
//Sort the array element using quick sort
public void quick_sort(int start, int end, int[] data)
{
if (start < end)
{
int pv = pivit(start, data, end);
quick_sort(start, pv - 1, data);
quick_sort(pv + 1, end, data);
}
}
public void replace(Node root, int[] auxiliary)
{
if (root != null)
{
replace(root.left, auxiliary);
root.data = auxiliary[this.location];
this.location += 1;
replace(root.right, auxiliary);
}
}
public void bst()
{
int size = element_size(root);
//Create an array which are store the BT elements
int[] auxiliary = new int[size];
this.location = 0;
//Get all array elements
get_element(root, auxiliary);
//sort element
quick_sort(0, size - 1, auxiliary);
this.location = 0;
//Change sort element
replace(root, auxiliary);
}
public static void main(String[] args)
{
BinarySearchTree obj = new BinarySearchTree();
/* Make A Binary Tree
-----------------------
1
/ \
2 3
/ \ / \
4 5 6 7
/ \
8 9
*/
//insertion of binary Tree nodes
obj.root = new Node(1);
obj.root.left = new Node(2);
obj.root.left.right = new Node(5);
obj.root.left.right.left = new Node(8);
obj.root.right = new Node(3);
obj.root.right.right = new Node(7);
obj.root.right.left = new Node(6);
obj.root.right.left.right = new Node(9);
obj.root.left.left = new Node(4);
System.out.print(" Preorder \n");
obj.preorder(obj.root);
obj.bst();
System.out.print("\n After Convert BT to BST");
System.out.print("\n Preorder \n");
obj.preorder(obj.root);
}
}
Output
Preorder
1 2 4 5 8 3 6 9 7
After Convert BT to BST
Preorder
5 2 1 4 3 8 6 7 9
/*
C++ Program
Binary Tree to Binary Search Tree Conversion
*/
//Tree node
#include<iostream>
using namespace std;
class Node
{
public: int data;
Node * left;
Node * right;
Node(int data)
{
//Set data value of binary tree node
this-> data = data;
this->left = NULL;
this->right = NULL;
}
};
class BinarySearchTree
{
public: Node * root;
int location;
BinarySearchTree()
{
this->root = NULL;
this->location = 0;
}
void preorder(Node * root)
{
if (root != NULL)
{
cout << " " << root->data;
preorder(root->left);
preorder(root->right);
}
}
//Get the existing Binary search tree nodes
void get_element(Node * root, int auxiliary[])
{
if (root != NULL)
{
//add element into array
auxiliary[this->location] = root->data;
this->location += 1;
get_element(root->left, auxiliary);
get_element(root->right, auxiliary);
}
}
int element_size(Node * root)
{
if (root != NULL)
{
return element_size(root->left) + element_size(root->right) + 1;
}
return 0;
}
//Swap two nodes in array
void swap(int data[], int start, int end)
{
int back_up = data[start];
data[start] = data[end];
data[end] = back_up;
}
int pivit(int start, int data[], int end)
{
int temp = start - 1;
for (int i = start; i < end; ++i)
{
if (data[i] < data[end])
{
//swap data
swap(data, ++temp, i);
}
}
swap(data, temp + 1, end);
return temp + 1;
}
//Sort the array element using quick sort
void quick_sort(int start, int end, int data[])
{
if (start < end)
{
int pv = pivit(start, data, end);
quick_sort(start, pv - 1, data);
quick_sort(pv + 1, end, data);
}
}
void replace(Node * root, int auxiliary[])
{
if (root != NULL)
{
replace(root->left, auxiliary);
root->data = auxiliary[this->location];
this->location += 1;
replace(root->right, auxiliary);
}
}
void bst()
{
int size = element_size(this->root);
int auxiliary[size] ;
this->location = 0;
//Get all array elements
get_element(this->root, auxiliary);
//sort element
quick_sort(0, size - 1, auxiliary);
this->location = 0;
//Change sort element
replace(this->root, auxiliary);
}
};
int main()
{
BinarySearchTree obj = BinarySearchTree();
/* Make A Binary Tree
-----------------------
1
/ \
2 3
/ \ / \
4 5 6 7
/ \
8 9
*/
//insertion of binary Tree nodes
obj.root = new Node(1);
obj.root->left = new Node(2);
obj.root->left->right = new Node(5);
obj.root->left->right->left = new Node(8);
obj.root->right = new Node(3);
obj.root->right->right = new Node(7);
obj.root->right->left = new Node(6);
obj.root->right->left->right = new Node(9);
obj.root->left->left = new Node(4);
cout << " Preorder \n";
obj.preorder(obj.root);
obj.bst();
cout << "\n After Convert BT to BST";
cout << "\n Preorder \n";
obj.preorder(obj.root);
return 0;
}
Output
Preorder
1 2 4 5 8 3 6 9 7
After Convert BT to BST
Preorder
5 2 1 4 3 8 6 7 9
//Tree node
using System;
class Node
{
public int data;
public Node left;
public Node right;
public Node(int data)
{
//Set data value of binary tree node
this.data = data;
this.left = null;
this.right = null;
}
}
class BinarySearchTree
{
public Node root;
public int location;
public BinarySearchTree()
{
root = null;
location = 0;
}
public void preorder(Node root)
{
if (root != null)
{
Console.Write(" " + root.data);
preorder(root.left);
preorder(root.right);
}
}
//Get the existing Binary search tree nodes
public void get_element(Node root, int[] auxiliary)
{
if (root != null)
{
//add element into array
auxiliary[this.location] = root.data;
this.location += 1;
get_element(root.left, auxiliary);
get_element(root.right, auxiliary);
}
}
public int element_size(Node root)
{
if (root != null)
{
return element_size(root.left) + element_size(root.right) + 1;
}
return 0;
}
//Swap two nodes in array
public void swap(int[] data, int start, int end)
{
int back_up = data[start];
data[start] = data[end];
data[end] = back_up;
}
public int pivit(int start, int[] data, int end)
{
int temp = start - 1;
for (int i = start; i < end; ++i)
{
if (data[i] < data[end])
{
//swap data
swap(data, ++temp, i);
}
}
swap(data, temp + 1, end);
return temp + 1;
}
//Sort the array element using quick sort
public void quick_sort(int start, int end, int[] data)
{
if (start < end)
{
int pv = pivit(start, data, end);
quick_sort(start, pv - 1, data);
quick_sort(pv + 1, end, data);
}
}
public void replace(Node root, int[] auxiliary)
{
if (root != null)
{
replace(root.left, auxiliary);
root.data = auxiliary[this.location];
this.location += 1;
replace(root.right, auxiliary);
}
}
public void bst()
{
int size = element_size(root);
int[] auxiliary = new int[size];
this.location = 0;
//Get all array elements
get_element(root, auxiliary);
//sort element
quick_sort(0, size - 1, auxiliary);
this.location = 0;
//Change sort element
replace(root, auxiliary);
}
public static void Main(String[] args)
{
BinarySearchTree obj = new BinarySearchTree();
//insertion of binary Tree nodes
obj.root = new Node(1);
obj.root.left = new Node(2);
obj.root.left.right = new Node(5);
obj.root.left.right.left = new Node(8);
obj.root.right = new Node(3);
obj.root.right.right = new Node(7);
obj.root.right.left = new Node(6);
obj.root.right.left.right = new Node(9);
obj.root.left.left = new Node(4);
Console.Write(" Preorder \n");
obj.preorder(obj.root);
obj.bst();
Console.Write("\n After Convert BT to BST");
Console.Write("\n Preorder \n");
obj.preorder(obj.root);
}
}
Output
Preorder
1 2 4 5 8 3 6 9 7
After Convert BT to BST
Preorder
5 2 1 4 3 8 6 7 9
<?php
/*
Php Program
Binary Tree to Binary Search Tree Conversion
*/
//Tree node
class Node
{
public $data;
public $left;
public $right;
function __construct($data)
{
//Set data value of binary tree node
$this->data = $data;
$this->left = null;
$this->right = null;
}
}
class BinarySearchTree
{
public $root;
public $location;
function __construct()
{
$this->root = null;
$this->location = 0;
}
function preorder($root)
{
if ($root != null)
{
echo " ". $root->data;
$this->preorder($root->left);
$this->preorder($root->right);
}
}
//Get the existing Binary search tree nodes
function get_element($root, & $auxiliary)
{
if ($root != null)
{
//add element into array
$auxiliary[$this->location] = $root->data;
$this->location += 1;
$this->get_element($root->left, $auxiliary);
$this->get_element($root->right, $auxiliary);
}
}
function element_size($root)
{
if ($root != null)
{
return $this->element_size($root->left) + $this->element_size($root->right) + 1;
}
return 0;
}
//Swap two nodes in array
function swap( & $data, $start, $end)
{
$back_up = $data[$start];
$data[$start] = $data[$end];
$data[$end] = $back_up;
}
function pivit($start, & $data, $end)
{
$temp = $start - 1;
for ($i = $start; $i < $end; ++$i)
{
if ($data[$i] < $data[$end])
{
//swap data
$temp += 1;
$this->swap($data, $temp, $i);
}
}
$this->swap($data, $temp + 1, $end);
return $temp + 1;
}
//Sort the array element using quick sort
function quick_sort($start, $end, & $data)
{
if ($start < $end)
{
$pv = $this->pivit($start, $data, $end);
$this->quick_sort($start, $pv - 1, $data);
$this->quick_sort($pv + 1, $end, $data);
}
}
function replace($root, & $auxiliary)
{
if ($root != null)
{
$this->replace($root->left, $auxiliary);
$root->data = $auxiliary[$this->location];
$this->location += 1;
$this->replace($root->right, $auxiliary);
}
}
function bst()
{
$size = $this->element_size($this->root);
//Create an array which are store the BT elements
$auxiliary = array_fill(0, $size, null);
$this->location = 0;
//Get all array elements
$this->get_element($this->root, $auxiliary);
//sort element
$this->quick_sort(0, $size - 1, $auxiliary);
$this->location = 0;
//Change sort element
$this->replace($this->root, $auxiliary);
}
}
function main()
{
$obj = new BinarySearchTree();
//insertion of binary Tree nodes
$obj->root = new Node(1);
$obj->root->left = new Node(2);
$obj->root->left->right = new Node(5);
$obj->root->left->right->left = new Node(8);
$obj->root->right = new Node(3);
$obj->root->right->right = new Node(7);
$obj->root->right->left = new Node(6);
$obj->root->right->left->right = new Node(9);
$obj->root->left->left = new Node(4);
echo " Preorder \n";
$obj->preorder($obj->root);
$obj->bst();
echo "\n After Convert BT to BST";
echo "\n Preorder \n";
$obj->preorder($obj->root);
}
main();
Output
Preorder
1 2 4 5 8 3 6 9 7
After Convert BT to BST
Preorder
5 2 1 4 3 8 6 7 9
/*
Node Js Program
Binary Tree to Binary Search Tree Conversion
*/
//Tree node
class Node
{
constructor(data)
{
//Set data value of binary tree node
this.data = data;
this.left = null;
this.right = null;
}
}
class BinarySearchTree
{
constructor()
{
this.root = null;
this.location = 0;
}
preorder(root)
{
if (root != null)
{
process.stdout.write(" " + root.data);
this.preorder(root.left);
this.preorder(root.right);
}
}
//Get the existing Binary search tree nodes
get_element(root, auxiliary)
{
if (root != null)
{
//add element into array
auxiliary[this.location] = root.data;
this.location += 1;
this.get_element(root.left, auxiliary);
this.get_element(root.right, auxiliary);
}
}
element_size(root)
{
if (root != null)
{
return this.element_size(root.left) + this.element_size(root.right) + 1;
}
return 0;
}
//Swap two nodes in array
swap(data, start, end)
{
var back_up = data[start];
data[start] = data[end];
data[end] = back_up;
}
pivit(start, data, end)
{
var temp = start - 1;
for (var i = start; i < end; ++i)
{
if (data[i] < data[end])
{
//swap data
temp += 1;
this.swap(data, temp, i);
}
}
this.swap(data, temp + 1, end);
return temp + 1;
}
//Sort the array element using quick sort
quick_sort(start, end, data)
{
if (start < end)
{
var pv = this.pivit(start, data, end);
this.quick_sort(start, pv - 1, data);
this.quick_sort(pv + 1, end, data);
}
}
replace(root, auxiliary)
{
if (root != null)
{
this.replace(root.left, auxiliary);
root.data = auxiliary[this.location];
this.location += 1;
this.replace(root.right, auxiliary);
}
}
bst()
{
var size = this.element_size(this.root);
//Create an array which are store the BT elements
var auxiliary = Array(size).fill(null);
this.location = 0;
//Get all array elements
this.get_element(this.root, auxiliary);
//sort element
this.quick_sort(0, size - 1, auxiliary);
this.location = 0;
//Change sort element
this.replace(this.root, auxiliary);
}
}
function main()
{
var obj = new BinarySearchTree();
/* Make A Binary Tree
-----------------------
1
/ \
2 3
/ \ / \
4 5 6 7
/ \
8 9
*/
//insertion of binary Tree nodes
obj.root = new Node(1);
obj.root.left = new Node(2);
obj.root.left.right = new Node(5);
obj.root.left.right.left = new Node(8);
obj.root.right = new Node(3);
obj.root.right.right = new Node(7);
obj.root.right.left = new Node(6);
obj.root.right.left.right = new Node(9);
obj.root.left.left = new Node(4);
process.stdout.write(" Preorder \n");
obj.preorder(obj.root);
obj.bst();
process.stdout.write("\n After Convert BT to BST");
process.stdout.write("\n Preorder \n");
obj.preorder(obj.root);
}
main();
Output
Preorder
1 2 4 5 8 3 6 9 7
After Convert BT to BST
Preorder
5 2 1 4 3 8 6 7 9
# Python 3 Program
# Binary Tree to Binary Search Tree Conversion
# Tree node
class Node :
def __init__(self, data) :
# Set data value of binary tree node
self.data = data
self.left = None
self.right = None
class BinarySearchTree :
def __init__(self) :
self.root = None
self.location = 0
def preorder(self, root) :
if (root != None) :
print(" ", root.data, end = "")
self.preorder(root.left)
self.preorder(root.right)
# Get the existing Binary search tree nodes
def get_element(self, root, auxiliary) :
if (root != None) :
# add element into array
auxiliary[self.location] = root.data
self.location += 1
self.get_element(root.left, auxiliary)
self.get_element(root.right, auxiliary)
def element_size(self, root) :
if (root != None) :
return self.element_size(root.left) + self.element_size(root.right) + 1
return 0
# Swap two nodes in array
def swap(self, data, start, last) :
back_up = data[start]
data[start] = data[last]
data[last] = back_up
def pivit(self, start, data, last) :
temp = start - 1
i = start
while (i < last) :
if (data[i] < data[last]) :
# swap data
temp += 1
self.swap(data, temp, i)
i += 1
self.swap(data, temp + 1, last)
return temp + 1
# Sort the array element using quick sort
def quick_sort(self, start, last, data) :
if (start < last) :
pv = self.pivit(start, data, last)
self.quick_sort(start, pv - 1, data)
self.quick_sort(pv + 1, last, data)
def replace(self, root, auxiliary) :
if (root != None) :
self.replace(root.left, auxiliary)
root.data = auxiliary[self.location]
self.location += 1
self.replace(root.right, auxiliary)
def bst(self) :
size = self.element_size(self.root)
# Create an array which are store the BT elements
auxiliary = [None] * size
self.location = 0
# Get all array elements
self.get_element(self.root, auxiliary)
# sort element
self.quick_sort(0, size - 1, auxiliary)
self.location = 0
# Change sort element
self.replace(self.root, auxiliary)
def main() :
obj = BinarySearchTree()
# insertion of binary Tree nodes
# Make A Binary Tree
# -----------------------
# 1
# / \
# 2 3
# / \ / \
# 4 5 6 7
# / \
# 8 9
#
obj.root = Node(1)
obj.root.left = Node(2)
obj.root.left.right = Node(5)
obj.root.left.right.left = Node(8)
obj.root.right = Node(3)
obj.root.right.right = Node(7)
obj.root.right.left = Node(6)
obj.root.right.left.right = Node(9)
obj.root.left.left = Node(4)
print(" Preorder \n", end = "")
obj.preorder(obj.root)
obj.bst()
print("\n After Convert BT to BST", end = "")
print("\n Preorder \n", end = "")
obj.preorder(obj.root)
if __name__ == "__main__": main()
Output
Preorder
1 2 4 5 8 3 6 9 7
After Convert BT to BST
Preorder
5 2 1 4 3 8 6 7 9
# Ruby Program
# Binary Tree to Binary Search Tree Conversion
# Tree node
class Node
# Define the accessor and reader of class Node
attr_reader :data, :left, :right
attr_accessor :data, :left, :right
def initialize(data)
# Set data value of binary tree node
self.data = data
self.left = nil
self.right = nil
end
end
class BinarySearchTree
# Define the accessor and reader of class BinarySearchTree
attr_reader :root, :location
attr_accessor :root, :location
def initialize()
@root = nil
@location = 0
end
def preorder(root)
if (root != nil)
print(" ", root.data)
self.preorder(root.left)
self.preorder(root.right)
end
end
# Get the existing Binary search tree nodes
def get_element(root, auxiliary)
if (root != nil)
# add element into array
auxiliary[self.location] = root.data
self.location += 1
self.get_element(root.left, auxiliary)
self.get_element(root.right, auxiliary)
end
end
def element_size(root)
if (root != nil)
return self.element_size(root.left) + self.element_size(root.right) + 1
end
return 0
end
# Swap two nodes in array
def swap(data, start, last)
back_up = data[start]
data[start] = data[last]
data[last] = back_up
end
def pivit(start, data, last)
temp = start - 1
i = start
while (i < last)
if (data[i] < data[last])
# swap data
temp += 1
self.swap(data, temp, i)
end
i += 1
end
self.swap(data, temp + 1, last)
return temp + 1
end
# Sort the array element using quick sort
def quick_sort(start, last, data)
if (start < last)
pv = self.pivit(start, data, last)
self.quick_sort(start, pv - 1, data)
self.quick_sort(pv + 1, last, data)
end
end
def replace(root, auxiliary)
if (root != nil)
self.replace(root.left, auxiliary)
root.data = auxiliary[self.location]
self.location += 1
self.replace(root.right, auxiliary)
end
end
def bst()
size = self.element_size(@root)
# Create an array which are store the BT elements
auxiliary = Array.new(size) {nil}
self.location = 0
# Get all array elements
self.get_element(@root, auxiliary)
# sort element
self.quick_sort(0, size - 1, auxiliary)
self.location = 0
# Change sort element
self.replace(@root, auxiliary)
end
end
def main()
obj = BinarySearchTree.new()
# insertion of binary Tree nodes
# Make A Binary Tree
# -----------------------
# 1
# / \
# 2 3
# / \ / \
# 4 5 6 7
# / \
# 8 9
#
obj.root = Node.new(1)
obj.root.left = Node.new(2)
obj.root.left.right = Node.new(5)
obj.root.left.right.left = Node.new(8)
obj.root.right = Node.new(3)
obj.root.right.right = Node.new(7)
obj.root.right.left = Node.new(6)
obj.root.right.left.right = Node.new(9)
obj.root.left.left = Node.new(4)
print(" Preorder \n")
obj.preorder(obj.root)
obj.bst()
print("\n After Convert BT to BST")
print("\n Preorder \n")
obj.preorder(obj.root)
end
main()
Output
Preorder
1 2 4 5 8 3 6 9 7
After Convert BT to BST
Preorder
5 2 1 4 3 8 6 7 9
/*
Scala Program
Binary Tree to Binary Search Tree Conversion
*/
//Tree node
class Node(var data: Int,
var left: Node,
var right: Node)
{
def this(data: Int)
{
//Set data value of binary tree node
this(data,null,null);
}
}
class BinarySearchTree(var root: Node,
var location: Int)
{
def this()
{
this(null,0);
}
def preorder(root: Node): Unit = {
if (root != null)
{
print(" " + root.data);
preorder(root.left);
preorder(root.right);
}
}
//Get the existing Binary search tree nodes
def get_element(root: Node, auxiliary: Array[Int]): Unit = {
if (root != null)
{
//add element into array
auxiliary(this.location) = root.data;
this.location += 1;
get_element(root.left, auxiliary);
get_element(root.right, auxiliary);
}
}
def element_size(root: Node): Int = {
if (root != null)
{
return element_size(root.left) + element_size(root.right) + 1;
}
return 0;
}
//Swap two nodes in array
def swap(data: Array[Int], start: Int, last: Int): Unit = {
var back_up: Int = data(start);
data(start) = data(last);
data(last) = back_up;
}
def pivit(start: Int, data: Array[Int], last: Int): Int = {
var temp: Int = start - 1;
var i: Int = start;
while (i < last)
{
if (data(i) < data(last))
{
//swap data
temp += 1;
swap(data, temp, i);
}
i += 1;
}
swap(data, temp + 1, last);
return temp + 1;
}
//Sort the array element using quick sort
def quick_sort(start: Int, last: Int, data: Array[Int]): Unit = {
if (start < last)
{
var pv: Int = pivit(start, data, last);
quick_sort(start, pv - 1, data);
quick_sort(pv + 1, last, data);
}
}
def replace(root: Node, auxiliary: Array[Int]): Unit = {
if (root != null)
{
replace(root.left, auxiliary);
root.data = auxiliary(this.location);
this.location += 1;
replace(root.right, auxiliary);
}
}
def bst(): Unit = {
var size: Int = element_size(root);
//Create an array which are store the BT elements
var auxiliary: Array[Int] = Array.fill[Int](size)(0);
this.location = 0;
//Get all array elements
get_element(root, auxiliary);
//sort element
quick_sort(0, size - 1, auxiliary);
this.location = 0;
//Change sort element
replace(root, auxiliary);
}
}
object Main
{
def main(args: Array[String]): Unit = {
var obj: BinarySearchTree = new BinarySearchTree();
//insertion of binary Tree nodes
/* Make A Binary Tree
-----------------------
1
/ \
2 3
/ \ / \
4 5 6 7
/ \
8 9
*/
obj.root = new Node(1);
obj.root.left = new Node(2);
obj.root.left.right = new Node(5);
obj.root.left.right.left = new Node(8);
obj.root.right = new Node(3);
obj.root.right.right = new Node(7);
obj.root.right.left = new Node(6);
obj.root.right.left.right = new Node(9);
obj.root.left.left = new Node(4);
print(" Preorder \n");
obj.preorder(obj.root);
obj.bst();
print("\n After Convert BT to BST");
print("\n Preorder \n");
obj.preorder(obj.root);
}
}
Output
Preorder
1 2 4 5 8 3 6 9 7
After Convert BT to BST
Preorder
5 2 1 4 3 8 6 7 9
/*
Swift Program
Binary Tree to Binary Search Tree Conversion
*/
//Tree node
class Node
{
var data: Int;
var left: Node? ;
var right: Node? ;
init(_ data: Int)
{
//Set data value of binary tree node
self.data = data;
self.left = nil;
self.right = nil;
}
}
class BinarySearchTree
{
var root: Node? ;
var location: Int;
init()
{
self.root = nil;
self.location = 0;
}
func preorder(_ root: Node? )
{
if (root != nil)
{
print(" ", root!.data, terminator: "");
self.preorder(root!.left);
self.preorder(root!.right);
}
}
//Get the existing Binary search tree nodes
func get_element(_ root: Node? , _ auxiliary : inout[Int])
{
if (root != nil)
{
//add element into array
auxiliary[self.location] = root!.data;
self.location += 1;
self.get_element(root!.left, &auxiliary);
self.get_element(root!.right, &auxiliary);
}
}
func element_size(_ root: Node? ) -> Int
{
if (root != nil)
{
return self.element_size(root!.left) + self.element_size(root!.right) + 1;
}
return 0;
}
//Swap two nodes in array
func swap(_ data: inout[Int], _ start: Int, _ last: Int)
{
let back_up: Int = data[start];
data[start] = data[last];
data[last] = back_up;
}
func pivit(_ start: Int, _ data: inout[Int], _ last: Int) -> Int
{
var temp: Int = start - 1;
var i: Int = start;
while (i < last)
{
if (data[i] < data[last])
{
//swap data
temp += 1;
self.swap(&data, temp, i);
}
i += 1;
}
self.swap(&data, temp + 1, last);
return temp + 1;
}
//Sort the array element using quick sort
func quick_sort(_ start: Int, _ last: Int, _ data: inout[Int])
{
if (start < last)
{
let pv: Int = self.pivit(start, &data, last);
self.quick_sort(start, pv - 1, &data);
self.quick_sort(pv + 1, last, &data);
}
}
func replace(_ root: Node? , _ auxiliary : inout[Int])
{
if (root != nil)
{
self.replace(root!.left, &auxiliary);
root!.data = auxiliary[self.location];
self.location += 1;
self.replace(root!.right, &auxiliary);
}
}
func bst()
{
let size: Int = self.element_size(self.root);
//Create an array which are store the BT elements
var auxiliary: [Int] = Array(repeating: 0, count: size);
self.location = 0;
//Get all array elements
self.get_element(self.root, &auxiliary);
//sort element
self.quick_sort(0, size - 1, &auxiliary);
self.location = 0;
//Change sort element
self.replace(self.root, &auxiliary);
}
}
func main()
{
let obj: BinarySearchTree = BinarySearchTree();
//insertion of binary Tree nodes
/* Make A Binary Tree
-----------------------
1
/ \
2 3
/ \ / \
4 5 6 7
/ \
8 9
*/
obj.root = Node(1);
obj.root!.left = Node(2);
obj.root!.left!.right = Node(5);
obj.root!.left!.right!.left = Node(8);
obj.root!.right = Node(3);
obj.root!.right!.right = Node(7);
obj.root!.right!.left = Node(6);
obj.root!.right!.left!.right = Node(9);
obj.root!.left!.left = Node(4);
print(" Preorder \n", terminator: "");
obj.preorder(obj.root);
obj.bst();
print("\n After Convert BT to BST", terminator: "");
print("\n Preorder \n", terminator: "");
obj.preorder(obj.root);
}
main();
Output
Preorder
1 2 4 5 8 3 6 9 7
After Convert BT to BST
Preorder
5 2 1 4 3 8 6 7 9
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