LeetCode: Closest Binary Search Tree Value Posted on February 16, 2018July 26, 2020 by braindenny Closest Binary Search Tree Value Similar Problems: Closest Binary Search Tree Value II CheatSheet: Leetcode For Code Interview CheatSheet: Common Code Problems & Follow-ups Tag: #binarytree, #recursive 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. Github: code.dennyzhang.com Credits To: leetcode.com Leave me comments, if you have better ways to solve. ## https://code.dennyzhang.com/closest-binary-search-tree-value ## Basic Ideas: binary search ## ## After checking the root, only need to check either left or right subtree ## ## Complexity: Time O(log(n)), Space O(1) # Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def closestValue(self, root: TreeNode, target: float) -> int: res = root.val while root: res = min(res, root.val, key=lambda x: abs(x-target)) if target > root.val: root = root.right else: root = root.left return res ## https://code.dennyzhang.com/closest-binary-search-tree-value ## Basic Ideas: ## If the exact match, return ## If current node is bigger than the target, we get a starting value. ## Then check left sub-tree ## If smaller, get a starting value. Then check right sub-tree ## ## Complexity: Time O(log(n)), Space O(1) ## # Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def closestValue(self, root, target): """ :type root: TreeNode :type target: float :rtype: int """ if root is None: return None res = root.val min_diff = abs(target - root.val) if min_diff == 0: return res check_left, check_right = False, False if root.val > target: # no need to explore the right check_left = True else: check_right = True if check_left and root.left: l_closest = self.closestValue(root.left, target) if abs(target - l_closest) < min_diff: res = l_closest if check_right and root.right: r_closest = self.closestValue(root.right, target) if abs(target - r_closest) < min_diff: res = r_closest return res Post Views: 8