Closest Value in a Binary Search Tree (BST) Without using an iterator, create a

Question

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 closestValue( 10 ) should return 14 closestValue (20) should return 21. closestValue( 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

------Method1------

Algorithm---->
If target value is present in given BST, then it’s the node having minimum absolute difference.
If target value is less than the value of current node then move to the left child.
If target value is greater than the value of current node then move to the right child.

-----------C++ code for this algorithm------------
I am taking two arguments in the function closestValue-root and the target value.The algorithm will work the same in this case also.

#include<bits/stdc++.h>
using namespace std;

//Binary tree-key,pointer to left child,pointer to right child
struct Node
{
int key;
struct Node* left, *right;
};

struct Node* newnode(int key)
{
struct Node* node = new (struct Node);
node->key = key;
node->left = node->right = NULL;
return (node);
}

void helper(struct Node *ptr, int k, int &min_diff,
int &min_diff_key)
{
if (ptr == NULL)
return ;

// If k itself is present
if (ptr->key == k)
{
min_diff_key = k;
return;
}

// update min_diff and min_diff_key by checking
// current node value
if (min_diff > abs(ptr->key - k))
{
min_diff = abs(ptr->key - k);
min_diff_key = ptr->key;
}

// if k is less than ptr->key then move in
// left subtree else in right subtree
if (k < ptr->key)
helper(ptr->left, k, min_diff, min_diff_key);
else
maxDiffUtil(ptr->right, k, min_diff, min_diff_key);
}

int closestValue(Node *root, int k)
{
int min_diff = INT_MAX, min_diff_key = -1;

helper(root, k, min_diff, min_diff_key);

return min_diff_key;
}

// Driver program to run the case
int main()
{
struct Node *root = newnode(9);
root->left = newnode(4);
root->right = newnode(17);
root->left->left = newnode(3);
root->left->right = newnode(6);
root->left->right->left = newnode(5);
root->left->right->right = newnode(7);
root->right->right = newnode(22);
root->right->right->left = newnode(20);
int k = 18;
cout << maxDiff(root, k);
return 0;
}

Output--17

Time complexity-Time complexity : O(h),h being the height of binary tree.

For more test cases,you can change the values present in the main function.

-----Method2--------

A simple solution for this problem is to store Inorder traversal of given binary search tree in an auxiliary array and then by taking absolute difference of each element find the node having minimum absolute difference with given target value K in linear time.

Though it is not an efficient solution,therefore,i am not providing you with its c++ code as it would be a bad practise.In worst case,if you don't remember the efficient solution,it will come handy to you.

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.