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.

The Idea: Perform a regular binary search, except rather than searching for the element explicitly, continually update the closest difference with the target value.

Complexity: O(logN) time and O(|height|) space

class Solution:
    def closestValue(self, root, target):
        """
        :type root: TreeNode
        :type target: float
        :rtype: int
        """

        min_diff = [sys.maxsize]
        min_val = [root.val]

        def search(root):
            if not root:
                return
            cur_min_diff = abs(root.val - target)
            if cur_min_diff < min_diff[0]:
                min_diff[0] = cur_min_diff
                min_val[0] = root.val

            if target < root.val:
                return search(root.left)
            else:
                return search(root.right)

        search(root)
        return min_val[0]

Python Solution

Same idea, but now iterative.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

import sys


class Solution:
    def closestValue(self, root, target):
        """
        :type root: TreeNode
        :type target: float
        :rtype: int
        """

        dist = sys.maxsize
        closest_val = sys.maxsize

        while root:
            cur_dist = abs(root.val - target)
            if cur_dist < dist:
                closest_val = root.val 
                dist = cur_dist
            if target > root.val:
                root = root.right
            else:
                root = root.left

        return closest_val