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

// 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;
}

// 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;
}

// 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;
}

272. Closest Binary Search Tree Value II