Project Closest Value in a Binary Search Tree (BST) Without using an iterator, c
ID: 3739386 • Letter: P
Question
Project Closest Value in a Binary Search Tree (BST) Without using an iterator, create a new method called closestValue) that takes an Object value and then locates a value in the tree that is closest to this Object. If the root of the tree is NULL, your method should throw an InvalidTreeArgument exception. The prototype for this method should be the following object BST::closestvalue(object value); For example, suppose you have the following BST 32 24 41 21 28 36 47 14 25 31 39 closestValuel 10) should return 14. closestValue (20) should return 21 closestValuel 42 ) should return 41. HINT: The answer returned will come from the nodes found on the path followed as if the Object parameter is getting inserted into the tree. HINT: Use recursion and pass additional parameters that keep track of the closest value you have seen so far. Pass this closest value by reference so that future recursive calls can update this parameter as additional nodes are encountered Create a test driver program that exercises each of these methods, prints the tree and the results of each operation,Explanation / Answer
#include <stdio.h>
#include<stdlib.h>
int count=0;
/* A binary tree node has data, pointer to left child
and a pointer to right child */
struct node
{
int data;
struct node* left;
struct node* right;
};
/* Helper function that allocates a new node
with the given data and NULL left and right
pointers. */
struct node* newNode(int data)
{
struct node* node = (struct node*)
malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;
return(node);
}
/* Give a binary search tree and a number,
inserts a new node with the given number in
the correct place in the tree. Returns the new
root pointer which the caller should then use
(the standard trick to avoid using reference
parameters). */
struct node* insert(struct node* node, int data)
{
/* 1. If the tree is empty, return a new,
single node */
if (node == NULL)
return(newNode(data));
else
{
/* 2. Otherwise, recur down the tree */
if (data <= node->data)
node->left = insert(node->left, data);
else
node->right = insert(node->right, data);
/* return the (unchanged) node pointer */
return node;
}
}
/* Given a non-empty binary search tree,
return the minimum data value found in that
tree. Note that the entire tree does not need
to be searched. */
int closestValue(struct node* node, int value) {
struct node* current = node;
if(current == NULL && count == 0)
{
printf("Tree is empty");
exit(1);
}
if(current == NULL && count !=0)
{
return (current->data);
}
if(-1 <= (current->data - value) && (current->data - value) <= 1)
{
return (current->data);
}
else if(current->data > value)
{
count++;
return closestValue(current->left, value);
}
else if(current->data < value)
{
count++;
return closestValue(current->right, value);
}
else
return 0;
}
/* Driver program to test sameTree function*/
int main()
{
struct node* root = NULL;
int k;
clrscr();
root = insert(root, 4);
insert(root, 2);
insert(root, 1);
insert(root, 3);
insert(root, 6);
insert(root, 5);
printf("Enter value to search");
scanf("%d", &k);
if (closestValue(root, k)!=0)
printf(" Closest value in BST is %d", closestValue(root, k));
else
printf(" Closest value in BST is %d", root->data);
getch();
return 0;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.