javabinary-treelowest-common-ancestor

LCA of Binary Tree - Need some Advice


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 ?


Solution

  • 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.