# 270. 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.

**Example:**

```
Input: root = [4,2,5,1,3], target = 3.714286

    4
   / \
  2   5
 / \
1   3

Output: 4
```

```cpp
// Naive Recursion
void helper(TreeNode* node, double target, int& res) {
    if (!node) return;
    if (abs(target - res) > abs(target - node->val))
        res = node->val;
    helper(node->left, target, res);
    helper(node->right, target, res);
}
int closestValue(TreeNode* root, double target) { // time: O(n); space: O(n) for the worst case, O(log(n)) for the average
    if (!root) return -1;
    int res = root->val;
    helper(root, target, res);
    return res;
}
```

```cpp
// Optimized Recursion
int closestValue(TreeNode* root, double target) { // time: O(log(n)) for the average, O(n) for the worst case; space: O(n) for the worst case, O(log(n)) for the average
    int res = root->val;
    if (target < root->val && root->left) {
        int left = closestValue(root->left, target);
        if (abs(target - res) > abs(target - left))
            res = left;
    } else if (target > root->val && root->right) {
        int right = closestValue(root->right, target);
        if (abs(target - res) > abs(target - right))
            res = right;
    }
    return res;
}
```

```cpp
// Optimized Iteration
int closestValue(TreeNode* root, double target) { // time: O(log(n)) for the average, O(n) for the worst case; space: O(1)
    int res = root->val;
    TreeNode* cur = root;
    while (cur) {
        if (abs(target - cur->val) < abs(target - res))
            res = cur->val;
        cur = target < cur->val ? cur->left : cur->right;
    }
    return res;
}
```

{% content-ref url="272.-closest-binary-search-tree-value-ii" %}
[272.-closest-binary-search-tree-value-ii](https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/tree/272.-closest-binary-search-tree-value-ii)
{% endcontent-ref %}
