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.


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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s