https://leetcode.com/problems/closest-binary-search-tree-value/
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.
Code
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