270

270. Closest Binary Search Tree Value (Easy)

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

Companies:
Facebook

Related Topics:
Binary Search, Tree

Similar Questions:

• Count Complete Tree Nodes (Medium)
• Closest Binary Search Tree Value II (Hard)
• Search in a Binary Search Tree (Easy)

Solution 1.

// OJ: https://leetcode.com/problems/closest-binary-search-tree-value/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(logN)
class Solution {
public:
    int closestValue(TreeNode* root, double target) {
        double dist = abs(target - root->val);
        if (dist < .5) return root->val;
        if (root->val < target) {
            if (!root->right) return root->val;
            int right = closestValue(root->right, target);
            return dist < abs(target - right) ? root->val : right;
        }
        if (!root->left) return root->val;
        int left = closestValue(root->left, target);
        return dist < abs(target - left) ? root->val : left;
    }
};

Solution 2.

// OJ: https://leetcode.com/problems/closest-binary-search-tree-value/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(logN)
// Ref: https://leetcode.com/problems/closest-binary-search-tree-value/discuss/70331/Clean-and-concise-java-solution
class Solution {
public:
    int closestValue(TreeNode* root, double target) {
        int ans = root->val;
        while (root) {
            if (abs(target - root->val) < abs(target - ans)) ans = root->val;
            root = root->val > target ? root->left : root->right;
        }
        return ans;
    }
};