Closest Node
by Isai Damier, Android Engineer @ Google

/***************************************************************************
 * Author: Isai Damier
 * Title: Closest Node
 * Project: geekviewpoint
 * Package: algorithms
 *
 * Statement:
 *   Retrieve the node whose value is closest to the given value.
 *
 * Time Complexity of Solution:
 *   Best = const; Average = O(log(n)); Worst = O(n).
 *
 * Technical Details: From a logic viewpoint, if the given element is on the
 *   tree, then it is closest to itself. Furthermore, At any given time, a
 *   value falls between two other values, such as x <= el <= y, where el
 *   falls between x and y. Therefore, as el is searched through the tree,
 *   there only needs to track two values: low and high. In the end,
 *   whichever of low and high is closer to el is returned; i.e. the
 *   wrapping node is return. (In case of a tie, high is returned.)
 *
 **************************************************************************/ 
 public Node closestNode(int el) {
  if (null == root) {
    return null;
  }
  Node n = root;
  Node low = null, high = null;
  while (n != null && el != n.data) {
    if (el < n.data) {
      high = n;
      n = n.left;
    } else {
      low = n;
      n = n.right;
    }
  }//while

  if (null != n) {
    return n;
  }
  if (null != high && null != low) {
    return (high.data - el) > (el - low.data) ? low : high;
  }
  if (null != high) {
    return high;
  }
  return low;
}

import org.junit.Test;
import static org.junit.Assert.*;

public class BSTTest {

/**
   * Test of closestNode method, of class BST.
   */
  @Test
  public void testClosestNode() {
    System.out.println(""closestNode"");
    BST bst = new BST();
    assertNull(bst.closestNode(275));
    int[] treeTape = {200, 100, 300, 50, 150, 250, 350, 25, 75, 125,
      175, 225, 275, 325, 375, 35, 212, 312, 400};
    for (int i : treeTape) {
      bst.add(i);
    }

    //load data into tree
    for (int i : treeTape) {
      bst.add(i);
    }
    assertEquals(treeTape.length, bst.size());//has correct size

    //test closestNode
    assertEquals(200, bst.closestNode(200).data);
    assertEquals(400, bst.closestNode(500).data);
    assertEquals(25, bst.closestNode(1).data);
    assertEquals(175, bst.closestNode(180).data);
    assertEquals(200, bst.closestNode(190).data);
    assertEquals(350, bst.closestNode(356).data);
    assertEquals(35, bst.closestNode(30).data);
    assertEquals(225, bst.closestNode(219).data);
    assertEquals(212, bst.closestNode(218).data);
    assertEquals(150, bst.closestNode(150).data);

    assertEquals(treeTape.length, bst.size());//has correct size
  }
}