modification to LCA code for binary tree to check if node is present in Java

Question

I have this code, which calculates Least common Ancestor of given two nodes in a Binary tree. Currently, it assumes both nodes are present. I can write a helper method just to check if the nodes are present and then call the LCABT method. That would require traversing the tree twice. I am wondering if there is a way to check and handle a situation when node is not present with my current code.

//LCA of Binary tree
            public static Node LCABT(Node root, int v1, int v2){
                if (root==null)
                    return null;
                if (root.data==v1 || root.data==v2){
                    return root;
                }
                Node left = LCABT(root.left,v1,v2);
                Node right = LCABT(root.right,v1,v2);

                if(left!=null && right!=null)
                    return root;
                else if (left!=null)
                     return left;
                else  if (right!=null)
                       return right;
                return null;
            }

Answer 1

Make the function return a pair (state, lca). state must be one of:

0: Neither v1 nor v2 appear at or under root; lca is meaningless.
1: Only v1 appears at or under root; lca is meaningless.
2: Only v2 appears at or under root; lca is meaningless.
3: Both v1 and v2 appear at or under root, and have LCA equal to lca.

The function should begin by checking for base cases:

LCABT(Node root, int v1, int v2) {
    if (root == null) then return (0, null);

Otherwise, recurse on its left and right children, to see if one of them solves the problem all by itself:

    (s1, lca1) = LCABT(root.left, v1, v2);
    (s2, lca2) = LCABT(root.right, v1, v2);

and if either s1 or s2 is 3, then the LCA has already been found (it's either lca1 or lca2, respectively) and can be returned immediately. (In fact, you can even obtain a speedup by checking whether s1 == 3 before making the second call to LCABT(): if it is, then we already have the LCA and don't need the second call.)

    if (s1 == 3) then return (3, lca1);
    if (s2 == 3) then return (3, lca2);

Otherwise, set s = s1 | s2 (i.e. bitwise OR). If s == 3 then we know that root is the LCA, but we haven't yet considered all ways in which it can be the LCA: it can still be the LCA when only one of v1 and v2 is present at or under its children, provided that the other value is at root itself:

    s = s1 | s2;
    if (root.data == v1) then s = s | 1;
    if (root.data == v2) then s = s | 2;

Now all cases in which root is the LCA imply s == 3, so if s == 3 then we can return (3, root) immediately:

    if (s == 3) then return (3, root);

Otherwise, at most one of v1 and v2 is at or under root, so we should return a value indicating which one it is:

    return (s, null);
}

Finally, the original top-level call to LCABT() should obviously regard the function as succeeding only when it returns a state value of 3.

Another advantage of this algorithm over yours is that it will not be fooled by duplicate copies of either v1 or v2 in the tree.