Leetcode 270: Closest Binary Search Tree Value

https://leetcode.com/problems/closest-binary-search-tree-value/

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

class Solution(object):
    def closestValue(self, root, target):
        """
        :type root: TreeNode
        :type target: float
        :rtype: int
        """
        if root is None:
            return None
        self.m = sys.maxint
        self.helper(root, target)
        return self.closest

    def helper(self, root, target):
        if self.m > abs(root.val - target):
            self.closest = root.val
            self.m = abs(root.val - target)
        
        if root.left and target < root.val:
            self.helper(root.left, target)
        if root.right and target > root.val:
            self.helper(root.right, target)

 

Idea

If a value is larger than root.val, then difference between the value and any node in the root’s left tree must be larger than that between the value and the root itself. If a value is smaller than root.val, then difference between the value and any node in the root’s right tree must be larger than that between the value and the root itself.

The time complexity of this algorithm is O(logN), where N is the total number of nodes in the BST and we assume the BST is balanced.

 

Reference

https://leetcode.com/discuss/54438/4-7-lines-recursive-iterative-ruby-c-java-python