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.

**My Solution**

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

### Like this:

Like Loading...

*Related*