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;
}
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.