# Immediate Common Parentby Isai Damier, Android Engineer @ Google

```  #=====================================================================
# 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 ) )
treeTape = [200, 100, 300, 50, 150, 250, 350, 25, 75, 125,
175, 225, 275, 325, 375, 35, 212, 312, 400]
for i in treeTape:

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
```