Immediate Common Parent
by Isai Damier

  #=====================================================================
  # Author: Isai Damier
  # Title: Immediate Common Parent
  # Project: geekviewpoint
  # Package: algorithms
  #
  # Statement:
  #   Find the immediate common parent of the two given elements.
  #
  # Time Complexity of Solution:
  #   Best = const; Average = O(log(n)); Worst = O(n).
  #
  # Technical Details: It is assumed that either of the given elements
  #   may actually not be on the tree. It is further understood that n
  #   cannot be the common parent of n and n.left, for example.
  #   Therefore, a second variable p (n's parent) is tracked to account
  #   for cases where the two elements being tested, a and b, have an
  #   ancestral relationship themselves.
  #
  #=====================================================================
 
 
class BST( object ):

  def __init__( self ):
      self.root = None


  def getRoot( self ):
    return self.root

  def immediateCommonParent( self, a, b ):
    if None == self.find( a ) or None == self.find( b ):
      return None
    n, p = self.root, None
    large, small = 0, 0
    if a > b:
      large = a
      small = b
    else:
      large = b
      small = a

    while n is not None:
      if large < n.data:
        p = n
        n = n.left
      elif small > n.data:
        p = n
        n = n.right
      else:
        break;

    if a == n.data or b == n.data:
      return p

    return n;
import unittest
from algorithms.BST import BST
from cStringIO import StringIO
import sys
class Test( unittest.TestCase ):
  #=====================================================================
  # Test of immediateCommonParent method, of class BST.
  #=====================================================================
  def testImmediateCommonParent( self ):
    bst = BST()

    self.assertIsNone( bst.immediateCommonParent( 35, 400 ) )
    # load data into tree
    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 )

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

    # test immediateCommonParent
    self.assertEquals( 200, bst.immediateCommonParent( 35, 400 ).data )
    self.assertEquals( 300, bst.immediateCommonParent( 312, 250 ).data )
    self.assertIsNone( bst.immediateCommonParent( 2, 275 ) )
    self.assertIsNone( bst.immediateCommonParent( 2, 500 ) )
    self.assertIsNone( bst.immediateCommonParent( 200, 350 ) )
    self.assertEquals( 350, bst.immediateCommonParent( 375, 375 ).data )
    self.assertEquals( 100, bst.immediateCommonParent( 125, 150 ).data )

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