Question:

In a binary integer value tree, find the lowest level common ancestor of two values.

http://www.glassdoor.com/Interview/In-a-binary-integer-value-tree-find-the-lowest-level-common-ancestor-of-two-values-QTN_219955.htm

// class TreeNode{
//   int val;
//   TreeNode left; 
//   TreeNode right;
//  }
//
// Lowest common ancestor question
//
// If it is a BST tree
// Given root, if two inputs are both smaller than root, the common ancestor must be on the root left.
// If two inputs are both bigger than root, the common ancestor must be on the right
// otherwise, the root is the common ancestor.
public TreeNode findLowestCommonAncestor(TreeNode root, TreeNode a, TreeNode b)
{
    // Input validations
    // root cannot be null.
    // a || b cannot be null.
    // a and b must be node in the tree.
    
    if (a.val < root.val && b.val < root.val)
        return findLowestCommonAncestor(root.left, a, b);
    else if (a.val > root.val && b.val > root.val)
        return findLowestCommonAncestor(root.right, a, b);
    else
        return root;
}

// For BT
// We can Buttom-Up
// O(n)
public TreeNode findLowestCommonAncestor(TreeNode root, TreeNode a, TreeNode b)
{
    if (root == null)
        return null;

    if (root == a || root == b)
        return root;
        
    TreeNode findLeft = findLowestCommonAncestor(root.left, a, b);
    TreeNode findRight = findLowestCommonAncestor(root.right, a, b);
    if (findLeft != null && findRight != null)
        return root;
    else if (findLeft != null)
        return findLeft;
    else
        return findRight ;
}

// Or we can top down
//
// If it is just a normal BT
// Given a root
// Define hit(root, a, b):int
// as the number of nodes in root.
// If a and b are both in root, hit = 2
// if only a in root or only b in root, hit = 1
// otherwise hit = 0
//
// O(n^2) : for each node, iterate the whole tree.
public TreeNode findLowestCommonAncestor(TreeNode root, TreeNode a, TreeNode b)
{
  int lefthit = hit(root, a, b);
  if (lefthit == 1)
      return root;
  else if (lefthit == 2)
      return findLowestCommonAncestor(root.left, a, b);
  else
      return findLowestCommonAncestor(root.right, a, b);
}

// Assume a != b
private int hit(TreeNode node, TreeNode a, TreeNode b)
{
  if (node == null || a == null || b == null)
      return 0;
      
  int r = 0;
  if (node == a)
  {
      a = null;
      r ++;
  }
  if (node == b)
  {
      b = null;
      r ++;
  }
  
  return r + hit(node.left, a, b) + hit(node.right, a, b);
}

[Twitter] Lowest Level Common Ancestor