Get Lowest Common Ancester of Two Nodes in A Tree

if node 1 is in left tree and node 2 is in right tree, then root is the lowest common ancestor

if both node1 and node 2 are in left tree, then do same recursion to left tree, until lowest ancestor is found

Same logic is applied when node 1 in right tree and node 2 in left tree...

A helper function is required to tell if a node is in a tree.

   public static TreeNode getLastCommonParentRec(TreeNode root, TreeNode n1, TreeNode n2) { 
        if (findNodeRec(root.left, n1)) {             
            if (findNodeRec(root.right, n2)) { 
                return root;                            
            } else {        
                return getLastCommonParentRec(root.left, n1, n2); 
            } 
        } else {              
            if (findNodeRec(root.left, n2)) {
                return root; 
            } else {            
                return getLastCommonParentRec(root.right, n1, n2);
            } 
        } 
    }

public static boolean findNodeRec(TreeNode root, TreeNode node) { 
        if (root == null || node == null) { 
            return false; 
        } 
        //root the first, this is preorder traversal
        if (root == node) { 
            return true; 
        } 
 
        // find in left tree the first 
        boolean found = findNodeRec(root.left, node); 
        if (!found) {       // if it is not in left tree, then find it in right tree
            found = findNodeRec(root.right, node); 
        } 
        return found; 
    }