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