Java Least Common Ancestor
// Find the least common ancestor or lca()
public static Node lca(Node n1, Node n2, Node r){
if (r != null){
if (r.data == n1.data || r.data == n2.data){
return r;
}else {
Node left = lca(n1, n2, r.left);
Node right= lca(n1, n2, r.right);
if (left != null && right != null){
return r;
}else if(left != null && right == null){
return left;
}else if(left == null && right != null){
return right;
}
}
}
return null;
}
Least Common Ancestor:
5 is the LCA of 1 and 9
5 is the LCA of 5 and 1
10 is the LCA of 9 and 15