Interview Questions
Return closest value from binary search tree
Given integer value k and binary search tree of integers, return value closest to value k from the tree.
View Solution
int GetClosestValue(Node *root, int k)
{
if (!root)
throw exception();
int closest = root->value;
Node *tmp = root;
while (tmp)
{
// check if we found new closest value
if (std::abs(tmp->value - k) < std::abs(closest - k))
closest = tmp->value;
// check if we can return early
if (k == closest)
break;
// decide if we should left or right
if (k < tmp->value)
tmp = tmp->left;
else
tmp = tmp->right;
}
return closest;
}