# [leetcode] Closest Binary Search Tree Value

Closest Binary Search Tree Value

Given a non-empty binary search tree and a target value, find the value in the BST that is closest to the target.

Note:

• Given target value is a floating point.
• You are guaranteed to have only one unique value in the BST that is closest to the target.

10/17/2015 Update Iteration version

```/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
int closestValue(TreeNode* root, double target) {
int ans = root->val;
while(root != nullptr){
ans = fabs(target - ans) < fabs(target - root->val)? ans: root->val;
if(target > root->val){
root = root->right;
}
else{
root = root->left;
}
}
return ans;
}
};```

Recursive version

```/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
int closestValue(TreeNode* root, double target) {
int tmp;
if(target > root->val && root->right){
tmp = closestValue(root->right, target);
}
else if(target < root->val && root->left){
tmp = closestValue(root->left, target);
}
else{
return root->val;
}

return abs(tmp - target) < abs(root->val - target)? tmp: root->val;
}
};```

```/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
int closestValue(TreeNode* root, double target) {
int ans = root->val;
BST(root, ans, target);
return ans;
}
void BST(TreeNode * root, int & ans, double target){
if(root == NULL) return ;
if(abs(root->val - target) < abs(ans - target)){
ans = root->val;
}
if(root->val < target){//BUG HERE , root->val not ans
BST(root->right, ans, target);
}
else if (root->val > target){
BST(root->left, ans, target);
}
else{
return ;
}
}
};```

This site uses Akismet to reduce spam. Learn how your comment data is processed.