package com.interview.tree;

/**
 * http://www.geeksforgeeks.org/lowest-common-ancestor-binary-tree-set-1/
 * This program assumes that both key val1 and val2 are present in tree under root.
 * If it is possible that val1 or val2 wont be present you need extra check to see that
 * whatever node is returned has val1 or val2 under it.
 * Test cases:
 * Both val1 and val2 exists in the tree
 * val1 is ancestor of val2
 * val2 is ancestor of val1
 * val1 and val2 have different ancestor
 * val1 and val2 are siblings
 */
public class LowestCommonAncestorInBinaryTree {

    public Node lowestCommonAncestor(int val1, int val2,Node root){
        if(root == null){
            return null;
        }
        if(root.data == val1 || root.data == val2){
            return root;
        }
        
        Node left = lowestCommonAncestor(val1, val2, root.left);
        Node right = lowestCommonAncestor(val1, val2, root.right);
        
        if(left != null && right != null){
            return root;
        }
        return left != null ? left : right;
    }
    
    public static void main(String args[]){
        BinaryTree bt = new BinaryTree();
        Node root = null;
        root = bt.addNode(10, root);
        root = bt.addNode(25, root);
        root =  bt.addNode(-10, root);
        root = bt.addNode(0, root);
        root = bt.addNode(-20, root);
        root = bt.addNode(15, root);
        root = bt.addNode(18, root);
        root = bt.addNode(35, root);
        
        LowestCommonAncestorInBinaryTree lca = new LowestCommonAncestorInBinaryTree();
        Node result = lca.lowestCommonAncestor(0, -20, root);
        System.out.print(result.data);
    }
}

@@ -33,489 +33,147 @@
 %0A * 
-http://www.geeksforgeeks.org/lowest-common-ancestor-binary-tree-set-1/%0A * This program assumes that both key val1 and val2 are present in tree under root.%0A * If it is possible that val1 or val2 wont be present you need extra check to see that%0A * whatever node is returned has val1 or val2 under it.%0A * Test cases:%0A * Both val1 and val2 exists in the tree%0A * val1 is ancestor of val2%0A * val2 is ancestor of val1%0A * val1 and val2 have different ancestor%0A * val1 and val2 are siblings
+Date 04/27/2016%0A * @author Tushar Roy%0A *%0A * Find lowest common ancestor in binary tree.%0A *%0A * Time complexity O(n)%0A * Space complexity O(h)
 %0A */
@@ -243,56 +243,38 @@
 de l
-owestCommonAncestor(int val1, int val2,
+ca(Node root, Node n1, 
 Node 
-root
+n2
 )%7B%0A 
@@ -348,28 +348,21 @@
  if(root
-.data
  == 
-val
+n
 1 %7C%7C roo
@@ -366,20 +366,13 @@
 root
-.data
  == 
-val
+n
 2)%7B%0A
@@ -440,40 +440,11 @@
  = l
-owestCommonAncestor(val1, val2, 
+ca(
 root
@@ -448,16 +448,24 @@
 oot.left
+, n1, n2
 );%0A     
@@ -485,61 +485,32 @@
  = l
-owestCommonAncestor(val1, val2, root.right);%0A        
+ca(root.right, n1, n2);%0A
 %0A   
@@ -638,624 +638,6 @@
   %7D%0A
-    %0A    public static void main(String args%5B%5D)%7B%0A        BinaryTree bt = new BinaryTree();%0A        Node root = null;%0A        root = bt.addNode(10, root);%0A        root = bt.addNode(25, root);%0A        root =  bt.addNode(-10, root);%0A        root = bt.addNode(0, root);%0A        root = bt.addNode(-20, root);%0A        root = bt.addNode(15, root);%0A        root = bt.addNode(18, root);%0A        root = bt.addNode(35, root);%0A        %0A        LowestCommonAncestorInBinaryTree lca = new LowestCommonAncestorInBinaryTree();%0A        Node result = lca.lowestCommonAncestor(0, -20, root);%0A        System.out.print(result.data);%0A    %7D%0A
 %7D%0A

update lca