[4.6] Frist(Lowest) Commonacestor

1. Example

1. Not a binary search tree,
http://www.geeksforgeeks.org/lowest-common-ancestor-binary-tree-set-1
Time complexity of the above solution is O(n)Attempt#1
Attempt#2
http://articles.leetcode.com/2011/07/lowest-common-ancestor-of-a-binary-tree-part-i.html

        _______3______
       /              \
    ___5__          ___1__
   /      \        /      \
   6      _2       0       8
         /  \
         7   4

the LCA of nodes 5and 1 is 3. 
Please note that LCA for nodes 5 and 4 is 5.
Please note that LCA for nodes 7 and 4 is 2. (although 5,3 are also ancestors, but not the lowest)

2. binary search tree, we could do a modified find on the two nodes and see where the paths diverge.

http://www.geeksforgeeks.org/lowest-common-ancestor-in-a-binary-search-tree/

Time complexity is O(h) where h is height of tree
Recursive, Iterativehttp://algorithms.tutorialhorizon.com/files/2014/11/LCA-in-Binary-Search-Tree.png

2. Implementation

// LCA for Binary Tree

// Time:O(n)
// 1. Recursive #1
public TreeNode LCA(TreeNode root, TreeNode p1, TreeNode p2)
{


     if ( isChild(root.left, p1) && isChild(root.right, p2) )
           return LCA(root.left, p1 ,p2);
     if ( isChild(root.right,p1) && isChild(root.right,p2) )
           return LCA(root.right, p1,p2);
     return root;
   

}
private boolean isChild(TreeNode root, TreeNode p)
{
     if (root == null)
          return false;
     if (root == p)
          return true;
     return isChild(root.left, p) || isChild(root.right, p);
}


// 2. Recursive #2

// Case1: If there are two nodes on one of the sides, then we have
// to check if the child node on this side is p or q (because in this 
// case the current node is the common ancestor).
// If the child node is neither p nor q, we should continue to search 
// further (starting from the child).

// Case2:  If one of the searched nodes (p or q) is located on the right 
// side of the current node, then the other node is located on the other 
// side. Thus the current node is the common ancestor

public class Solution
{


      static int TWO_NODES_FOUND = 2;
      static int ONE_NODE_FOUND = 1;
      static int NO_NODE_FOUND = 0;
   




      public TreeNode LCA(TreeNode root, TreeNode p1, TreeNode p2)
      {

             // Same node and only node node below
             if ( p2 == p1 && (root.left == p2 || root.right == p1) )
                 return root;


             int nodesFromLeft =  isChild(root.left, p1,p2);
             if (  nodesFromLeft == TWO_NODES_FOUND ) 
             {
                     if (root.left == p1 || root.left == p2)
                         return root.left;
                     else 
                         return LCA(root.left, p1,p2);
             }
             else if (  nodesFromLeft == ONE_NODE_FOUND   ) 
             {
                     if (root == p) return p;
                     else if (root == q) return q;
             }

             int nodeFromRight = isChild(root.right, p1, p2);
            if (  nodeFromRight == TWO_NODES_FOUND ) 
             {
                     if (root.right == p1 || root.right == p2)
                         return root.left;
                     else 
                         return LCA(root.right, p1,p2);
             }
             else if (  nodeFromRight == ONE_NODE_FOUND   ) 
             {
                     if (root == p) return p;
                     else if (root == q) return q;
             }




             if (  nodeFromLeft == ONE_NODE_FOUND && nodeFromRight == ONE_NODE_FOUND  )
                  return root;
             else 
                  return null;


      }






      // Check how many nodes (p1, p2 ,p1 and p2, none) under this root
      // Output: 0(NO_NODES_FOUND),1(ONE_NODE_FOUND),2(TWO_NODES_FOUND)
      private int isChild(TreeNode root, TreeNode p1, TreeNode p2)
      {


/*
             int ret= NO_NODES_FOUND;
           


             if (root==null)
                   return NO_NODES_FOUND;
             if (root == p1 || root == p2)
                   ret+=1;


             // isChild(root.left..) || isChild(root.right,..)
             ret += isChild(root.left, p1,p2);
             if ( ret = TWO_NODES_FOUND )   //FOUND p1 and p2
             {
                 return ret;
             }
             return ret + isChild(root.right, p1, p2);
*/

             int ret = 0;
             ret += isChild(root, p1)?1:0;
             ret += isChild(root, p2)?1:0;
             return ret;
                  

      }


      private boolean isChild(TreeNode root, TreeNode p)
      {
          if (root == null)
              return false;
          if (root == p)
              return true;
          return isChild(root.left, p) || isChild(root.right, p);
      }
}

// LCA for Binary Search Tree

// Time :O(logn) = O(h), h is the height of the tree
// 1. Recursive Space:O(n)
public TreeNode LCA(TreeNode root, TreeNode p1, TreeNode p2)
{


     // Base case
     if ( root == null )
         return null;
  

     if ( root.val > p1.val && root.val > p2.val ) 
           return LCA( root.left, p1, p2 );
     else if ( root.val < p1.val && root.val < p2.val )
           return LCA( root.right, p1, p2); 
     return root;


}
// 2. Iterative Space:O(1)
public TreeNode LCA(TreeNode root, TreeNode p1, TreeNode p2)
{
      while ( root != null )
      {
           if ( root.val > p1.val && root.val > p2.val  ) 
              root = root.left;
           else if (  root.val < p1.val && root.val < p2.val  )
              root = root.right;
           else 
              break;
      }


      return root;

}

3. similar Ones