AC non-recursive java code of lgn average time complexity, corner cases taken into account.

• A simple and clean code can be referred to the following, which is lgn average time complexity:
java code

However, the aforementioned code does not consider corner cases, such as:

1. at least one of root, p, and q is null;

2. at least one of p & q is not a node in the tree rooted at root.

The following code with lgn average time complexity can deal with above corner cases.

``````    private boolean binarySearch(TreeNode t, TreeNode n){
if(t==null) return false;
if(t.val == n.val) return true;
return n.val<t.val?
binarySearch(t.left, n) :
binarySearch(t.right, n);
}
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root==null || p==null || q==null ||
!binarySearch(root, p) || !binarySearch(root, q))
return null;
if(p.val == q.val) return p;
TreeNode r = root;
while((p.val-r.val)*(q.val-r.val) > 0)
r = p.val<r.val? r.left : r.right;
return r;
}
``````

• I don't think it is a non-recursive solution...your binarySearch function is recursive.

• Here is my non-recursive solution:

``````public class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
TreeNode lowest = null;

while (root != null) {
if (p.val == root.val || q.val == root.val || (p.val < root.val && q.val > root.val) || (p.val > root.val && q.val < root.val)) {
lowest = root;
break;
} else if (p.val < root.val && q.val < root.val) {
root = root.left;
} else root = root.right;
}

return lowest;
}
}``````

• You are right, and thanks for let me know it.

• The code will fail for the corner case: p or q is not in the tree. Nevertheless, this is a neat solution.

• It p or q doesn't exit, eventually the while loop will end because root turns null, and lowest will return null because I defined it out of the while loop.

• fail case: [2, 1, 3], 0, 4. root.val=2, lowest = root will be returned. In fact, however, p & q do NOT have a LCA.

• Yes, you are right, anyway, my solution is AC now, looks like they don't have such test case. But you are right, probably I should check if p or/and q doesn't exist.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.