Least Common Ancestor

Find the lowest common ancestor in an unordered binary tree given two values in the tree.

Lowest common ancestor : the lowest common ancestor (LCA) of two nodes v and w in a tree or directed acyclic graph (DAG) is the lowest (i.e. deepest) node that has both v and w as descendants.

Example :

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

For the above tree, the LCA of nodes 5 and 1 is 3.

LCA = Lowest common ancestor

Please note that LCA for nodes 5 and 4 is 5.

• You are given 2 values. Find the lowest common ancestor of the two nodes represented by val1 and val2

• No guarantee that val1 and val2 exist in the tree. If one value doesn’t exist in the tree then return -1.

• There are no duplicate values.

• You can use extra memory, helper functions, and can modify the node struct but, you can’t add a parent pointer.

class Solution {
    boolean foundP = false;
    boolean foundQ = false;

    public int lowestCommonAncestor(TreeNode root, int p, int q) {
        if (root == null)
            return -1;
        if (root.val == p || root.val == q) {
            foundP = root.val == p ? true : foundP;
            foundQ = root.val == q ? true : foundQ;
        }
        int left = lowestCommonAncestor(root.left, p, q);
        int right = lowestCommonAncestor(root.right, p, q);
        if (root.val == p || root.val == q) {
            return root.val;
        } else {
            if (left != -1 && right != -1)
                return root.val;
            else if (left != -1)
                return left;
            else if (right != -1)
                return right;
            return -1;
        }
    }

    public int lca(TreeNode root, int p, int q) {
        foundP = false;
        foundQ = false;
        int ans = lowestCommonAncestor(root, p, q);
        if (foundP && foundQ)
            return ans;
        return -1;
    }
}