Lowest Common Ancestor with parent node

/**
 * Definition of ParentTreeNode:
 * 
 * class ParentTreeNode {
 *     public ParentTreeNode parent, left, right;
 * }
 */
public class Solution {
    /**
     * @param root: The root of the tree
     * @param A, B: Two node in the tree
     * @return: The lowest common ancestor of A and B
     */
    public ParentTreeNode lowestCommonAncestorII(ParentTreeNode root,
                                                 ParentTreeNode A,
                                                 ParentTreeNode B) {
        // Write your code here   
        // Non recursive
        // http://wiki.ruihan.org/index.php/Lowest_Common_Ancestor_II

        if (root == null)
            return root;

        Set<ParentTreeNode> set = new HashSet();
        while (A != null || B != null) {
            if (A != null) {
                if (set.contains(A)){
                    return A;
                } else
                    set.add(A);

                A = A.parent;
            }

            if (B != null) {
                if (set.contains(B)) {
                    return B;
                } else 
                    set.add(B);
                B = B.parent;
            }

        }

        return null;
    }
}

Lowest Common Ancestor

Assuming 2 nodes are existing

Return value is not guaranteed to be the LCA, it is LCA or A or B.

/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */
public class Solution {
    /**
     * @param root: The root of the binary search tree.
     * @param A and B: two nodes in a Binary.
     * @return: Return the least common ancestor(LCA) of the two nodes.
     */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode node1 , TreeNode node2) {
        // write your code here
        if (root == null)
            return null;

        // root is one of nodes, return root
        if (root == node1 || root == node2) {
            return root;
        }

        // Divide
        TreeNode left = lowestCommonAncestor(root.left, node1, node2);
        TreeNode right = lowestCommonAncestor(root.right, node1, node2);

        // Conquer
        if (left != null && right != null) {
            return root;
        } 

        if (left != null)
            return left;
        if (right != null)
            return right;
        return null;
    }
}

Lowest Common Ancestor

node A or node B may not exist in tree.

/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */
public class Solution {
    /**
     * @param root The root of the binary tree.
     * @param A and B two nodes
     * @return: Return the LCA of the two nodes.
     */
    public TreeNode lowestCommonAncestor3(TreeNode root, TreeNode a, TreeNode b) {
        // write your code here
        if (root == null)
            return null;
        Result res = helper(root, a ,b);
        if (res.hasA && res.hasB)
            return res.node;
        else 
            return null;
    }

    public Result helper(TreeNode root, TreeNode a, TreeNode b) {
        if (root == null)
            return new Result(null, false, false);


        Result left = helper(root.left, a, b);
        Result right = helper(root.right, a, b);

        boolean hasA = left.hasA || right.hasA || root == a;
        boolean hasB = left.hasB || right.hasB || root == b;

        if (root == a || root == b)
            return new Result(root, hasA, hasB);


        if (left.node != null && right.node != null)
            return new Result(root, hasA, hasB);
        if (left.node != null)
            return new Result(left.node, hasA, hasB);
        if (right.node != null)
            return new Result(right.node, hasA, hasB);

        return new Result(null, hasA, hasB);
    }

    class Result{
        TreeNode node;
        boolean hasA;
        boolean hasB;

        public Result(TreeNode node, boolean a, boolean b) {
            this.node = node;
            this.hasA = a;
            this.hasB = b;
        }
    }
}