Find the closest element in Binary Search Tree

Here given code implementation process.
//C Program
//Find the closest element 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 find_difference(int a,int b)
{
a=a-b;
if(a<0)
{
a=-a;
}
return a;
}
//Get the minimum difference of three nodes
int compare_node(struct Node *head,
struct Node *left_p,
struct Node *right_p,
int element)
{
int result=0,a=0,b=0,c=0;
if(left_p != NULL && right_p != NULL)
{
a=find_difference(left_p->data,element);
b=find_difference(right_p->data,element);
c=find_difference(head->data,element);
//get min difference element
if((a<b)&&(a<c))
{
result = left_p->data;
}
else if(b<c && b<a)
{
result = right_p->data ;
}
else
{
result=head->data;
}
}
else if(left_p!=NULL)
{
a=find_difference(left_p->data,element);
c=find_difference(head->data,element);
if(c<a)
{
result = head->data;
}
else
{
result = left_p->data ;
}
}
else if(right_p != NULL)
{
b=find_difference(right_p->data,element);
c=find_difference(head->data,element);
if(c<a)
{
result = head->data;
}
else
{
result = right_p->data ;
}
}
else
{
result=head->data;
}
return result;
}
void find_node(struct Node *root,
struct Node *left_p,
struct Node *right_p,
int element)
{
if(root!=NULL)
{
if(root->data==element)
{
printf("Node %d closest element %d\n",element ,root->data );
}
else if(root->data > element)
{
if(root->left!=NULL)
{
find_node(root->left,left_p,root,element);
}
else
{
int result=compare_node(root,left_p,right_p,element);
printf("Node %d closest element %d\n",element ,result );
}
}
else
{
if(root->right!=NULL)
{
find_node(root->right,root,right_p,element);
}
else
{
int result=compare_node(root,left_p,right_p,element);
printf("Node %d closest element %d\n",element ,result );
}
}
}
}
void find_elements(struct Node *root,int element)
{
if(root!=NULL)
{
find_node(root,NULL,NULL,element);
}
else
{
printf("\nEmpty BST");
}
}
int main(){
struct Node*root = NULL;
//Add nodes in binary search tree
/*
10
/ \
3 19
/ \ / \
1 4 14 50
/ \
-3 2
*/
add(&root,10);
add(&root,3);
add(&root,19);
add(&root,1);
add(&root,4);
add(&root,-3);
add(&root,2);
add(&root,14);
add(&root,50);
//Test case
find_elements(root,4);
find_elements(root,17);
find_elements(root,11);
find_elements(root,25);
find_elements(root,16);
return 0;
}
Output
Node 4 closest element 4
Node 17 closest element 19
Node 11 closest element 10
Node 25 closest element 19
Node 16 closest element 14
/*
C++ Program
Find the closest element 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;
int result;
BinarySearchTree() {
this->root = NULL;
this->result = 0;
}
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";
}
}
int find_difference(int a, int b) {
a = a - b;
if (a < 0) {
a = -a;
}
return a;
}
void compare_node(Node *head, Node *left_p, Node *right_p, int element) {
int a = 0, b = 0, c = 0;
if (left_p != NULL && right_p != NULL) {
a = this->find_difference(left_p->data, element);
b = this->find_difference(right_p->data, element);
c = this->find_difference(head->data, element);
if ((a < b) && (a < c)) {
this->result = left_p->data;
} else
if (b < c && b < a) {
this->result = right_p->data;
} else {
this->result = head->data;
}
} else
if (left_p != NULL) {
a = this->find_difference(left_p->data, element);
c = this->find_difference(head->data, element);
if (c < a) {
this->result = head->data;
} else {
this->result = left_p->data;
}
} else
if (right_p != NULL) {
b = this->find_difference(right_p->data, element);
c = this->find_difference(head->data, element);
if (c < a) {
this->result = head->data;
} else {
this->result = right_p->data;
}
} else {
this->result = head->data;
}
}
void find_node(Node *head, Node *left_p, Node *right_p, int element) {
if (head != NULL) {
this->result = 0;
if (head->data == element) {
cout << "\nNode " << element << " closest element is " << head->data;
} else
if (head->data > element) {
if (head->left != NULL) {
this->find_node(head->left, left_p, head, element);
} else {
this->compare_node(head, left_p, right_p, element);
cout << "\nNode " << element << " closest element is " << this->result;
}
} else {
if (head->right != NULL) {
this->find_node(head->right, head, right_p, element);
} else {
this->compare_node(head, left_p, right_p, element);
cout << "\nNode " << element << " closest element is " << this->result;
}
}
}
}
void find_elements(int element) {
if (this->root != NULL) {
this->find_node(this->root, NULL, NULL, element);
} else {
cout << "\nEmpty BST";
}
}
};
int main() {
BinarySearchTree obj;
/*
10
/ \
3 19
/ \ / \
1 4 14 50
/ \
-3 2
*/
obj.add(10);
obj.add(3);
obj.add(19);
obj.add(1);
obj.add(4);
obj.add(-3);
obj.add(2);
obj.add(14);
obj.add(50);
obj.find_elements(4);
obj.find_elements(17);
obj.find_elements(11);
obj.find_elements(25);
obj.find_elements(16);
return 0;
}
Output
Node 4 closest element 4
Node 17 closest element 19
Node 11 closest element 10
Node 25 closest element 19
Node 16 closest element 14
//Java program
//Find the closest element in Binary Search Tree
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 int result;
BinarySearchTree() {
root = null;
result=0;
}
//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 int find_difference(int a, int b) {
a = a - b;
if (a < 0) {
a = -a;
}
return a;
}
//Get the minimum difference of three nodes
public void compare_node(Node head,
Node left_p,
Node right_p,
int element) {
int a = 0, b = 0, c = 0;
if (left_p != null && right_p != null) {
a = find_difference(left_p.data, element);
b = find_difference(right_p.data, element);
c = find_difference(head.data, element);
//get min difference element
if ((a < b) && (a < c)) {
this.result = left_p.data;
} else if (b < c && b < a) {
this.result = right_p.data;
} else {
this.result = head.data;
}
} else if (left_p != null) {
a = find_difference(left_p.data, element);
c = find_difference(head.data, element);
if (c < a) {
this.result = head.data;
} else {
this.result = left_p.data;
}
} else if (right_p != null) {
b = find_difference(right_p.data, element);
c = find_difference(head.data, element);
if (c < a) {
this.result = head.data;
} else {
this.result = right_p.data;
}
} else {
this.result = head.data;
}
}
public void find_node(Node head,
Node left_p,
Node right_p,
int element) {
if (head != null) {
this.result = 0;
if (head.data == element) {
System.out.print("\nNode " + element + " closest element is " + head.data);
}
else if (head.data > element) {
if (head.left != null) {
find_node(head.left, left_p, head, element);
} else {
compare_node(head, left_p, right_p, element);
System.out.print("\nNode " + element + " closest element is " + this.result);
}
} else {
if (head.right != null) {
find_node(head.right, head, right_p, element);
} else {
compare_node(head, left_p, right_p, element);
System.out.print("\nNode " + element + " closest element is " + this.result);
}
}
}
}
public void find_elements(int element) {
if (root != null) {
find_node(root, null, null, element);
} else {
System.out.print("\nEmpty BST");
}
}
public static void main(String[] args) {
BinarySearchTree obj = new BinarySearchTree();
//Add nodes in binary search tree
/*
10
/ \
3 19
/ \ / \
1 4 14 50
/ \
-3 2
*/
obj.add(10);
obj.add(3);
obj.add(19);
obj.add(1);
obj.add(4);
obj.add(-3);
obj.add(2);
obj.add(14);
obj.add(50);
//Test case
obj.find_elements(4);
obj.find_elements(17);
obj.find_elements(11);
obj.find_elements(25);
obj.find_elements(16);
}
}
Output
Node 4 closest element 4
Node 17 closest element 19
Node 11 closest element 10
Node 25 closest element 19
Node 16 closest element 14
//C# program
//Find the closest element in Binary Search Tree
using System;
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 int result;
BinarySearchTree() {
root = null;
result=0;
}
//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 int find_difference(int a, int b) {
a = a - b;
if (a < 0) {
a = -a;
}
return a;
}
//Get the minimum difference of three nodes
public void compare_node(Node head,
Node left_p,
Node right_p,
int element) {
int a = 0, b = 0, c = 0;
if (left_p != null && right_p != null) {
a = find_difference(left_p.data, element);
b = find_difference(right_p.data, element);
c = find_difference(head.data, element);
//get min difference element
if ((a < b) && (a < c)) {
this.result = left_p.data;
} else if (b < c && b < a) {
this.result = right_p.data;
} else {
this.result = head.data;
}
} else if (left_p != null) {
a = find_difference(left_p.data, element);
c = find_difference(head.data, element);
if (c < a) {
this.result = head.data;
} else {
this.result = left_p.data;
}
} else if (right_p != null) {
b = find_difference(right_p.data, element);
c = find_difference(head.data, element);
if (c < a) {
this.result = head.data;
} else {
this.result = right_p.data;
}
} else {
this.result = head.data;
}
}
public void find_node(Node head,
Node left_p,
Node right_p,
int element) {
if (head != null) {
this.result = 0;
if (head.data == element) {
Console.Write("\nNode " + element + " closest element is " + head.data);
}
else if (head.data > element) {
if (head.left != null) {
find_node(head.left, left_p, head, element);
} else {
compare_node(head, left_p, right_p, element);
Console.Write("\nNode " + element + " closest element is " + this.result);
}
} else {
if (head.right != null) {
find_node(head.right, head, right_p, element);
} else {
compare_node(head, left_p, right_p, element);
Console.Write("\nNode " + element + " closest element is " + this.result);
}
}
}
}
public void find_elements(int element) {
if (root != null) {
find_node(root, null, null, element);
} else {
Console.Write("\nEmpty BST");
}
}
public static void Main(String[] args) {
BinarySearchTree obj = new BinarySearchTree();
//Add nodes in binary search tree
/*
10
/ \
3 19
/ \ / \
1 4 14 50
/ \
-3 2
*/
obj.add(10);
obj.add(3);
obj.add(19);
obj.add(1);
obj.add(4);
obj.add(-3);
obj.add(2);
obj.add(14);
obj.add(50);
//Test case
obj.find_elements(4);
obj.find_elements(17);
obj.find_elements(11);
obj.find_elements(25);
obj.find_elements(16);
}
}
Output
Node 4 closest element 4
Node 17 closest element 19
Node 11 closest element 10
Node 25 closest element 19
Node 16 closest element 14
# Python 3 Program
# Find the closest element 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
self.result = 0
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 find_difference(self, a, b) :
a = a - b
if (a < 0) :
a = -a
return a
def compare_node(self, head, left_p, right_p, element) :
a = 0
b = 0
c = 0
if (left_p != None and right_p != None) :
a = self.find_difference(left_p.data, element)
b = self.find_difference(right_p.data, element)
c = self.find_difference(head.data, element)
if ((a < b) and(a < c)) :
self.result = left_p.data
elif (b < c and b < a) :
self.result = right_p.data
else :
self.result = head.data
elif (left_p != None) :
a = self.find_difference(left_p.data, element)
c = self.find_difference(head.data, element)
if (c < a) :
self.result = head.data
else :
self.result = left_p.data
elif (right_p != None) :
b = self.find_difference(right_p.data, element)
c = self.find_difference(head.data, element)
if (c < a) :
self.result = head.data
else :
self.result = right_p.data
else :
self.result = head.data
def find_node(self, head, left_p, right_p, element) :
if (head != None) :
self.result = 0
if (head.data == element) :
print("Node ", element ," closest element is ", head.data)
elif (head.data > element) :
if (head.left != None) :
self.find_node(head.left, left_p, head, element)
else :
self.compare_node(head, left_p, right_p, element)
print("Node ", element ," closest element is ", self.result)
else :
if (head.right != None) :
self.find_node(head.right, head, right_p, element)
else :
self.compare_node(head, left_p, right_p, element)
print("Node ", element ," closest element is ", self.result)
def find_elements(self, element) :
if (self.root != None) :
self.find_node(self.root, None, None, element)
else :
print("\nEmpty BST")
def main() :
obj = BinarySearchTree()
#
# 10
# / \
# 3 19
# / \ / \
# 1 4 14 50
# / \
# -3 2
#
obj.add(10)
obj.add(3)
obj.add(19)
obj.add(1)
obj.add(4)
obj.add(-3)
obj.add(2)
obj.add(14)
obj.add(50)
obj.find_elements(4)
obj.find_elements(17)
obj.find_elements(11)
obj.find_elements(25)
obj.find_elements(16)
if __name__ == "__main__":
main()
Output
Node 4 closest element 4
Node 17 closest element 19
Node 11 closest element 10
Node 25 closest element 19
Node 16 closest element 14
# Ruby Program
# Find the closest element 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, :result
attr_accessor :root, :result
def initialize()
@root = nil
@result = 0
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 find_difference(a, b)
a = a - b
if (a < 0)
a = -a
end
return a
end
def compare_node(head, left_p, right_p, element)
a = 0
b = 0
c = 0
if (left_p != nil and right_p != nil)
a = self.find_difference(left_p.data, element)
b = self.find_difference(right_p.data, element)
c = self.find_difference(head.data, element)
if ((a < b) and(a < c))
self.result = left_p.data
elsif (b < c and b < a)
self.result = right_p.data
else
self.result = head.data
end
elsif (left_p != nil)
a = self.find_difference(left_p.data, element)
c = self.find_difference(head.data, element)
if (c < a)
self.result = head.data
else
self.result = left_p.data
end
elsif (right_p != nil)
b = self.find_difference(right_p.data, element)
c = self.find_difference(head.data, element)
if (c < a)
self.result = head.data
else
self.result = right_p.data
end
else
self.result = head.data
end
end
def find_node(head, left_p, right_p, element)
if (head != nil)
self.result = 0
if (head.data == element)
print("\nNode ", element ," closest element is ", head.data)
elsif (head.data > element)
if (head.left != nil)
self.find_node(head.left, left_p, head, element)
else
self.compare_node(head, left_p, right_p, element)
print("\nNode ", element ," closest element is ", self.result)
end
else
if (head.right != nil)
self.find_node(head.right, head, right_p, element)
else
self.compare_node(head, left_p, right_p, element)
print("\nNode ", element ," closest element is ", self.result)
end
end
end
end
def find_elements(element)
if (@root != nil)
self.find_node(@root, nil, nil, element)
else
print("\nEmpty BST")
end
end
end
def main()
obj = BinarySearchTree.new()
#
# 10
# / \
# 3 19
# / \ / \
# 1 4 14 50
# / \
# -3 2
#
obj.add(10)
obj.add(3)
obj.add(19)
obj.add(1)
obj.add(4)
obj.add(-3)
obj.add(2)
obj.add(14)
obj.add(50)
obj.find_elements(4)
obj.find_elements(17)
obj.find_elements(11)
obj.find_elements(25)
obj.find_elements(16)
end
main()
Output
Node 4 closest element 4
Node 17 closest element 19
Node 11 closest element 10
Node 25 closest element 19
Node 16 closest element 14
<?php
/*
Php Program
Find the closest element 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;
public $result;
function __construct() {
$this->root = null;
$this->result = 0;
}
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 find_difference($a, $b) {
$a = $a - $b;
if ($a < 0) {
$a = -$a;
}
return $a;
}
public function compare_node($head, $left_p, $right_p, $element) {
$a = 0;
$b = 0;
$c = 0;
if ($left_p != null && $right_p != null) {
$a = $this->find_difference($left_p->data, $element);
$b = $this->find_difference($right_p->data, $element);
$c = $this->find_difference($head->data, $element);
if (($a < $b) && ($a < $c)) {
$this->result = $left_p->data;
} else
if ($b < $c && $b < $a) {
$this->result = $right_p->data;
} else {
$this->result = $head->data;
}
} else
if ($left_p != null) {
$a = $this->find_difference($left_p->data, $element);
$c = $this->find_difference($head->data, $element);
if ($c < $a) {
$this->result = $head->data;
} else {
$this->result = $left_p->data;
}
} else
if ($right_p != null) {
$b = $this->find_difference($right_p->data, $element);
$c = $this->find_difference($head->data, $element);
if ($c < $a) {
$this->result = $head->data;
} else {
$this->result = $right_p->data;
}
} else {
$this->result = $head->data;
}
}
public function find_node($head, $left_p, $right_p, $element) {
if ($head != null) {
$this->result = 0;
if ($head->data == $element) {
echo("\nNode ". $element ." closest element is ". $head->data);
} else
if ($head->data > $element) {
if ($head->left != null) {
$this->find_node($head->left, $left_p, $head, $element);
} else {
$this->compare_node($head, $left_p, $right_p, $element);
echo("\nNode ". $element ." closest element is ". $this->result);
}
} else {
if ($head->right != null) {
$this->find_node($head->right, $head, $right_p, $element);
} else {
$this->compare_node($head, $left_p, $right_p, $element);
echo("\nNode ". $element ." closest element is ". $this->result);
}
}
}
}
public function find_elements($element) {
if ($this->root != null) {
$this->find_node($this->root, null, null, $element);
} else {
echo("\nEmpty BST");
}
}
}
function main() {
$obj = new BinarySearchTree();
/*
10
/ \
3 19
/ \ / \
1 4 14 50
/ \
-3 2
*/
$obj->add(10);
$obj->add(3);
$obj->add(19);
$obj->add(1);
$obj->add(4);
$obj->add(-3);
$obj->add(2);
$obj->add(14);
$obj->add(50);
$obj->find_elements(4);
$obj->find_elements(17);
$obj->find_elements(11);
$obj->find_elements(25);
$obj->find_elements(16);
}
main();
Output
Node 4 closest element 4
Node 17 closest element 19
Node 11 closest element 10
Node 25 closest element 19
Node 16 closest element 14
/*
Node Js Program
Find the closest element in Binary Search Tree
*/
class Node {
constructor(value) {
this.data = value;
this.left = null;
this.right = null;
}
}
class BinarySearchTree {
constructor() {
this.root = null;
this.result = 0;
}
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");
}
}
find_difference(a, b) {
a = a - b;
if (a < 0) {
a = -a;
}
return a;
}
compare_node(head, left_p, right_p, element) {
var a = 0;
var b = 0;
var c = 0;
if (left_p != null && right_p != null) {
a = this.find_difference(left_p.data, element);
b = this.find_difference(right_p.data, element);
c = this.find_difference(head.data, element);
if ((a < b) && (a < c)) {
this.result = left_p.data;
} else
if (b < c && b < a) {
this.result = right_p.data;
} else {
this.result = head.data;
}
} else
if (left_p != null) {
a = this.find_difference(left_p.data, element);
c = this.find_difference(head.data, element);
if (c < a) {
this.result = head.data;
} else {
this.result = left_p.data;
}
} else
if (right_p != null) {
b = this.find_difference(right_p.data, element);
c = this.find_difference(head.data, element);
if (c < a) {
this.result = head.data;
} else {
this.result = right_p.data;
}
} else {
this.result = head.data;
}
}
find_node(head, left_p, right_p, element) {
if (head != null) {
this.result = 0;
if (head.data == element) {
process.stdout.write("\nNode " + element + " closest element is " + head.data);
} else
if (head.data > element) {
if (head.left != null) {
this.find_node(head.left, left_p, head, element);
} else {
this.compare_node(head, left_p, right_p, element);
process.stdout.write("\nNode " + element + " closest element is " + this.result);
}
} else {
if (head.right != null) {
this.find_node(head.right, head, right_p, element);
} else {
this.compare_node(head, left_p, right_p, element);
process.stdout.write("\nNode " + element + " closest element is " + this.result);
}
}
}
}
find_elements(element) {
if (this.root != null) {
this.find_node(this.root, null, null, element);
} else {
process.stdout.write("\nEmpty BST");
}
}
}
function main() {
var obj = new BinarySearchTree();
/*
10
/ \
3 19
/ \ / \
1 4 14 50
/ \
-3 2
*/
obj.add(10);
obj.add(3);
obj.add(19);
obj.add(1);
obj.add(4);
obj.add(-3);
obj.add(2);
obj.add(14);
obj.add(50);
obj.find_elements(4);
obj.find_elements(17);
obj.find_elements(11);
obj.find_elements(25);
obj.find_elements(16);
}
main();
Output
Node 4 closest element 4
Node 17 closest element 19
Node 11 closest element 10
Node 25 closest element 19
Node 16 closest element 14
/*
Swift 4 Program
Find the closest element 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? ;
var result: Int;
init() {
self.root = nil;
self.result = 0;
}
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 find_difference(_ a: Int, _ b: Int) -> Int {
var get_a = a;
get_a = a - b;
if (get_a < 0) {
get_a = -get_a;
}
return get_a;
}
func compare_node(_ head: Node? , _ left_p : Node? , _ right_p : Node? , _ element : Int) {
var a: Int = 0;
var b = 0;
var c = 0;
if (left_p != nil && right_p != nil) {
a = self.find_difference(left_p!.data, element);
b = self.find_difference(right_p!.data, element);
c = self.find_difference(head!.data, element);
if ((a < b) && (a < c)) {
self.result = left_p!.data;
} else
if (b < c && b < a) {
self.result = right_p!.data;
} else {
self.result = head!.data;
}
} else
if (left_p != nil) {
a = self.find_difference(left_p!.data, element);
c = self.find_difference(head!.data, element);
if (c < a) {
self.result = head!.data;
} else {
self.result = left_p!.data;
}
} else
if (right_p != nil) {
b = self.find_difference(right_p!.data, element);
c = self.find_difference(head!.data, element);
if (c < a) {
self.result = head!.data;
} else {
self.result = right_p!.data;
}
} else {
self.result = head!.data;
}
}
func find_node(_ head: Node? , _ left_p : Node? , _ right_p : Node? , _ element : Int) {
if (head != nil) {
self.result = 0;
if (head!.data == element) {
print("Node ", element ," closest element is ", head!.data);
} else
if (head!.data > element) {
if (head!.left != nil) {
self.find_node(head!.left, left_p, head, element);
} else {
self.compare_node(head, left_p, right_p, element);
print("Node ", element ," closest element is ", self.result);
}
} else {
if (head!.right != nil) {
self.find_node(head!.right, head, right_p, element);
} else {
self.compare_node(head, left_p, right_p, element);
print("Node ", element ," closest element is ", self.result);
}
}
}
}
func find_elements(_ element: Int) {
if (self.root != nil) {
self.find_node(self.root, nil, nil, element);
} else {
print("\nEmpty BST");
}
}
}
func main() {
let obj: BinarySearchTree = BinarySearchTree();
/*
10
/ \
3 19
/ \ / \
1 4 14 50
/ \
-3 2
*/
obj.add(10);
obj.add(3);
obj.add(19);
obj.add(1);
obj.add(4);
obj.add(-3);
obj.add(2);
obj.add(14);
obj.add(50);
obj.find_elements(4);
obj.find_elements(17);
obj.find_elements(11);
obj.find_elements(25);
obj.find_elements(16);
}
main();
Output
Node 4 closest element 4
Node 17 closest element 19
Node 11 closest element 10
Node 25 closest element 19
Node 16 closest element 14
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