Problem description:

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

1
2
3
4
5
    4
   / \
  2   5
 / \
1   3

Output: 4

Solution DFS:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def closestValue(self, root: Optional[TreeNode], target: float) -> int:
        '''
        either in one of the left or right subtree
        '''
        res, diff = root.val, float("inf")
        p = root
        while p:
            if abs(p.val - target) < diff:
                res = p.val
                diff = abs(p.val - target)
            p = p.left if target < p.val else p.right
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/**
 * 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) {
        double curmin= (double)root->val;
        helper(root, target, curmin);
        return curmin;
    }
    
    void helper(TreeNode* root, double target, double &curmin){
        if(!root) return;
        if((double)root->val == target){
            curmin= (double)root->val;
            return;
        }
        if(abs((double)root->val-target) < abs(curmin-target))
            curmin= (double)root->val;
        
        if(target< (double)root->val)
            helper(root->left, target, curmin);
        else
            helper(root->right, target, curmin);
    }
};

Solution BFS:

time complexity: $O(h)$
space complexity: $O(h)$
reference: