ClosestBinarySearchTreeValue.java

package tree;

/**
 * Created by gouthamvidyapradhan on 10/05/2017. Given a non-empty binary search tree and a target
 * value, find the value in the BST that is closest to the target.
 *
 * <p>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.
 *
 * <p>Solution: Simple dfs recursive algorithm to find the closest match. Worst case time complexity
 * is O(h) where h is height of the tree
 */
public class ClosestBinarySearchTreeValue {
  /** TreeNode */
  public static class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
      val = x;
    }
  }

  private double absDiff = Double.MAX_VALUE;
  private int closest;

  /**
   * Main method
   *
   * @param args
   * @throws Exception
   */
  public static void main(String[] args) throws Exception {
    TreeNode root = new TreeNode(10);
    root.left = new TreeNode(9);
    root.left.left = new TreeNode(8);
    System.out.println(new ClosestBinarySearchTreeValue().closestValue(root, 7.63354D));
  }

  /**
   * Find closest
   *
   * @param root Root node
   * @param target double target
   * @return closest value
   */
  public int closestValue(TreeNode root, double target) {
    if (root == null) return closest;
    if (Math.abs(target - root.val) < absDiff) {
      absDiff = Math.abs(target - root.val);
      closest = root.val;
    }
    if (root.val > target) return closestValue(root.left, target);
    else return closestValue(root.right, target);
  }
}