Closest Binary Search Tree Value

Problem: Closest Binary Search Tree Value

To do binary search, we try insert the float into the tree and record its left closest number and right closest number until we get a null node. We can update these two numbers while scanning the tree from root to leaf. Then we compare recorded numbers to get the result.

Code in Python:

class Solution(object):
    def closestValue(self, root, target):
        """
        :type root: TreeNode
        :type target: float
        :rtype: int
        """
        l, r = None, None
        while root:
            if target < root.val:
                if not r or r > root.val: r = root.val
                if root.left: root, prev = root.left, root.val
                else: break
            elif target > root.val:
                if not l or l < root.val: l = root.val
                if root.right: root, prev = root.right, root.val
                else: break
            else: return root.val

        if l == None: return r
        if r == None: return l
        if target-l < r-target:
            return l
        else:
            return r