C++ program to find the closest element in binary search tree
Description:
This Program is to print the closest elements present in the binary search tree.Let's learn it by the help of example:
Input : Tree elements are : 1 2 3 5 6 4 7 8 9 10
Output : Enter a element : 12
Closest Element is : 10
//C++ program to find the closest element in binary search tree
using namespace std;
// tree node
struct Node
{
int data;
Node *left, *right;
};
// returns a new tree Node
Node* newNode(int data)
{
Node* temp = new Node();
temp->data = data;
temp->left = temp->right = NULL;
return temp;
}
// A function to create binary search tree.
Node* Tree(Node* root, int data)
{
// Create node using data entered by user.
Node *temp = newNode(data);
Node *temp1 = new Node;
temp1 = root;
// If root is null then the node created.
if(root == NULL)
root = temp;
else
{
// Search the position for the new node to be inserted.
while(temp1 != NULL)
{
if(temp1->data < data )
{
if(temp1->right == NULL)
{
// If current node is NULL then the value will be inserted here and break.
temp1->right = temp;
break;
}
// Shift pointer to the left.
temp1 = temp1->right;
}
else if(temp1->data > data)
{
if(temp1->left == NULL)
{
temp1->left = temp;
break;
}
// Shift pointer to the left.
temp1 = temp1->left;
}
}
}
return root;
}
// Function to find node with minimum difference with given n
void minimum(struct Node *ptr, int n, int &min, int &min_diff)
{
if (ptr == NULL)
return ;
// If n itself is present
if (ptr->data == n)
{
min_diff= n;
return;
}
// update min and min_diff by checking current node value
if (min > abs(ptr->data - n))
{
min = abs(ptr->data - n);
min_diff = ptr->data;
}
// if n is less than ptr->data then move in left subtree else in right subtree
if (n < ptr->data)
minimum(ptr->left, n, min, min_diff);
else
minimum(ptr->right, n, min, min_diff);
}
int minDiff(Node *root, int n)
{
// Initialize minimum difference
int min = INT_MAX, min_diff = -1;
// Find value of min_diff (Closest data in tree with n)
minimum(root, n, min, min_diff);
return min_diff;
}
// Driver program to run the case
int main()
{
int n, arr[20],size;
Node *root = new Node;
root = NULL;
cout<<"Enter the size of array : ";
cin>>size;
cout<<"Enter the elements in array : ";
for(int i=0;i<size;i++)
{
cin>>arr[i];
}
// Construct the binary search tree.
for(int i = 0; i < size; i++)
root = Tree(root, arr[i]);
cout<<"Enter a element : ";
cin>>n;
cout <<"\nClosest Element is : "<< minDiff(root, n);
return 0;
}
Comments