Given a non-empty binary search tree and a target value, find the value in the BST that is closest to the target.
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.
In BST, the left child is always smaller than the root and the right child is always bigger. The basic idea is calculate the minimum difference in current root and update the closest value if difference is smaller. Then, depending on target is bigger or smaller compare to root, go right or left.
def find_closest(root, target): closest = root.val while root: # stop if root is null # Best case if root.val == target: return root.val # Get the min if abs(target-root.val) < abs(target-closest): closest = root.val # should find bigger nodes if target is big, to get closer if target > root.val: root = root.right else: root = root.left return closest