I know this question has been asked many times. I need some clarification on LCA of a Binary Tree (not BST). If I am trying to find LCA of two nodes(3,11) from the given tree :
_______1______
/ \
___2__ ___4__
/ \ / \
6 5 9 11
/ \
7 3
The Code returns 11 for (3,11).
// Binary Tree LCA not BST
private Node findLowestCommonAncestor(Node root, int value1, int value2) {
Node leftLCA = null;
Node rightLCA = null;
if (root == null) {
return null;
}
else {
int value = root.item;
if (value == value1 || value == value2) {
return root;
}
else {
leftLCA = findLowestCommonAncestor(root.left, value1, value2);
rightLCA = findLowestCommonAncestor(root.right, value1, value2);
if (leftLCA != null && rightLCA != null) {
return root;
}
return (leftLCA != null) ? leftLCA : rightLCA;
}
}
}
Here I am confused, It should be 4 right. Please correct me If I am wrong. Am I confusing here ? or Is it how LCA works ?
11
is the correct LCA of (3, 11)
in the tree you've shown.
I think you've perhaps overlooked the bit in the definition of LCA where elements are considered descendants of themselves:
...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, where we define each node to be a descendant of itself (so if v has a direct connection from w, w is the lowest common ancestor).
(emphasis mine)
Since 3
is a child of 11
, the LCA is 11
.