Find Immediate Common Parent
by 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 node 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.
 *
 **************************************************************************/ 
 public Node immediateCommonParent(int a, int b) {
  if (null == find(a) || null == find(b)) {
    return null;
  }
  Node n = root, p = null;
  int large, small;
  if (a > b) {
    large = a;
    small = b;
  } else {
    large = b;
    small = a;
  }

  while (null != n) {
    if (large < n.data) {
      p = n;
      n = n.left;
    } else if (small > n.data) {
      p = n;
      n = n.right;
    } else {
      break;
    }
  }
  if (a == n.data || b == n.data) {
    return p;
  }
  return n;
}

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

public class BSTTest {

/**
   * Test of immediateCommonParent method, of class BST.
   */
  @Test
  public void testImmediateCommonParent() {
    System.out.println(""immediateCommonParent"");
    BST bst = new BST();
    assertNull(bst.immediateCommonParent(35, 400));
    //load data into tree
    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);
    }
    assertEquals(treeTape.length, bst.size());//has correct size

    //test immediateCommonParent
    assertEquals(200, bst.immediateCommonParent(35, 400).data);
    assertEquals(300, bst.immediateCommonParent(312, 250).data);
    assertNull(bst.immediateCommonParent(2, 275));
    assertNull(bst.immediateCommonParent(2, 500));
    assertNull(bst.immediateCommonParent(200, 350));
    assertEquals(350, bst.immediateCommonParent(375, 375).data);
    assertEquals(100, bst.immediateCommonParent(125, 150).data);

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