LeetCode: Closest Binary Search Tree Value

## 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