BST Closest Node
by Isai Damier

  #=====================================================================
  # 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.)
  #
  #=====================================================================
 
 
class BST( object ):

  def __init__( self ):
      self.root = None


  def getRoot( self ):
    return self.root

  def closestNode( self, el ):
    if self.root is None:
      return None

    n = self.root
    high, low = None, None
    while n != None and el != n.data:
      if el < n.data:
        high = n
        n = n.left
      else:
        low = n
        n = n.right

    if n is not None:
      return n

    if None != high and None != low:
      return low if ( high.data - el ) > ( el - low.data ) else high

    if None != high:
      return high

    return low;
import unittest
from algorithms.BST import BST
from cStringIO import StringIO
import sys
class Test( unittest.TestCase ):
  #=====================================================================
  # Test of closestmethod, of class BST.
  #=====================================================================
  def testClosestNode( self ):
    bst = BST()

    self.assertIsNone( bst.closestNode( 275 ) )
    treeTape = [200, 100, 300, 50, 150, 250, 350, 25, 75, 125,
                      175, 225, 275, 325, 375, 35, 212, 312, 400]
    for i in treeTape:
      bst.add( i )


    # load data into tree
    for i in treeTape:
      bst.add( i )

    self.assertEquals( len( treeTape ), bst.size() ) # has correct size

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

    self.assertEquals( len( treeTape ), bst.size() ) # has correct size