algorithmlowest-common-ancestor

Lowest common ancestor Cracking coding Interview Solution


I am trying to understand one of the solutions in Cracking the Coding Interview page 129. This is about finding the lowest common ancestor. Please see code below. My questions are in the comments

In summary, my questions are:

1) For this line of code:

 if(root.left == p || root.left == q) return root.left;

Why return root.left and not root?

2) For these lines of code:

else if (nodesFromLeft == ONE_NODE_FOUND) {
     if (root == p) return p;  
     else if (root == q) return q; 
     }

Why return p if root==p, how is this the ancestor? Likewise for q.

Here is the entire code below:

 static int TWO_NODES_FOUND = 2;
 static int ONE_NODE_FOUND = 1;
 static int NO_NODES_FOUND = 0;

 // Checks how many “special” nodes are located under this root
 int covers(TreeNode root, TreeNode p, TreeNode q) {

      int ret = NO_NODES_FOUND;
      if (root == null) return ret;
      if (root == p || root == q) ret += 1;
      ret += covers(root.left, p, q);
      if(ret == TWO_NODES_FOUND) // Found p and q
           return ret;
 return ret + covers(root.right, p, q);
 }

 TreeNode commonAncestor(TreeNode root, TreeNode p, TreeNode q) {
      if (q == p && (root.left == q || root.right == q)) return root;

      int nodesFromLeft = covers(root.left, p, q); // Check left side
      if (nodesFromLeft == TWO_NODES_FOUND) {
           if(root.left == p || root.left == q) return root.left;//Qn1:See above
      else return commonAncestor(root.left, p, q);
      } 
      else if (nodesFromLeft == ONE_NODE_FOUND) {
           if (root == p) return p; //Qn 2: See qn above
           else if (root == q) return q; //Qn2: See qn above
      }
      int nodesFromRight = covers(root.right, p, q); // Check right side
      if(nodesFromRight == TWO_NODES_FOUND) {
           if(root.right == p || root.right == q) return root.right;
      else return commonAncestor(root.right, p, q);
      }
      else if (nodesFromRight == ONE_NODE_FOUND) {
           if (root == p) return p;
           else if (root == q) return q;
      }
      if (nodesFromLeft == ONE_NODE_FOUND && nodesFromRight == ONE_NODE_FOUND) return root;

      else return null;
 }

Solution

  • Why return root.left and not root?

    When nodesFromLeft is 2, then both p and q are under root.left. If one of them is root.left then that's the common ancestor. One is root.left and the other is below it.

    Why return p if root==p, how is this the ancestor?

    When nodesFromLeft is 1, then one node is under root.left and the other is either root, under root.right, or it doesn't exist in the tree. If it's root, then that's the ancestor. One not is root and the other is below it on the left.

    The case where it's under root.right or not in the tree is checked on the last two lines.