// Definition for a binary tree node.
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
public class Solution {
public static TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root == null  p == null  q == null)
{
return root;
}
// if p and q are both to the left and right of the root then
// root is the lca of p and q
if(root.val > p.val && root.val < q.val)
{
return root;
}
else if (root.val > p.val && root.val > q.val) // both p & q are to the left of root
{
return lowestCommonAncestor(root.left, p, q);
}
else // both p & q are to the right of root
{
return lowestCommonAncestor(root.right, p, q);
}
}
public static void main(String[] args)
{
TreeNode root = new TreeNode(2);
root.left = new TreeNode(1);
TreeNode ancestor = lowestCommonAncestor(root, root.left, null);
System.out.println(ancestor.val);
}
}
What is wrong with this lowest common ancestor solution?


You are assuming that
p.val < q.val
. This is not necessary. Also it is possible that either ofp
orq
might be the LCA themselves.To resolve both issues, you can replace this
if
clauseif(root.val > p.val && root.val < q.val) { return root; }
with
if(root.val >= Math.min(p.val, q.val) && root.val <= Math.max(p.val, q.val)) { return root; }
The minimum and maximum will ensure the test is correct and the equality will test out the cases when either of the input nodes is the LCA themselves.