# My Java Solution

• ``````public class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root.val > p.val && root.val > q.val){
return lowestCommonAncestor(root.left, p, q);
}else if(root.val < p.val && root.val < q.val){
return lowestCommonAncestor(root.right, p, q);
}else{
return root;
}
}
}``````

• A non-recursive version.

``````public class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
while (true) {
if (root.val > p.val && root.val > q.val)
root = root.left;
else if (root.val < p.val && root.val < q.val)
root = root.right;
else
return root;
}
}
}``````

• I guess the worst case running time is O(n). Right?

• Yes, for example, if most nodes in the tree only have one child (left child or right child) and node p and node q are in low position of the tree, then the program will not terminate until we find the correct node (by that time, we probably have nearly traversed the whole tree.)

• got it.............

• What if one of the target is not found in the BST? In which case, shouldn't the program return null?

• @fanofxiaofeng This is such an amazing solution :)

• I think a BST may contain the same keys.
So in some cases that are not among test cases of this problem, this solution will give a wrong answer.

• @fallcreek said in My Java Solution:

I think a BST may contain the same keys.
So in some cases that are not among test cases of this problem, this solution will give a wrong answer.

Agree with @fallcreek , in this case

``````6 (root)
\
6 (p)
\
6 (q)

``````

After all, this is a nice answer in case the problem specifically states every element in the BST are distinct.

Below is my code considering identical elements situation:

``````public class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
TreeNode[] ans = new TreeNode[1];
lca(Integer.MIN_VALUE, Integer.MAX_VALUE, root, p, q, ans);
return ans[0];
}

private int lca(int bot, int top, TreeNode r, TreeNode p, TreeNode q, TreeNode[] ans) {
if (r == null) return 0;
if ((p.val > top || p.val < bot) && (q.val > top || q.val < bot)) return 0;
int n1 = lca(bot, r.val, r.left, p, q, ans), n2 = lca(r.val, top, r.right, p, q, ans);
if (n1 > 1 || n2 > 1) return 2;
int n = n1 + n2 + ((r == p || r == q) ? 1 : 0);
if (n > 1) ans[0] = r;
return n;
}
}
``````

• @ofLucas Please help me understand this basic concept. Can a binary search tree have duplicate nodes? I was under the assumption that left will always be lower than the root and right will always be greater than the root. Please advise.

• @jingzhetian

The code is concise. However, what about the edge case: p or q is not in the tree? The problem does not define how to deal with the invalid input cases well.

• I have the same idea with this!

• Hi why is the non-recursive version different from the following:

``````public class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
while (root.val > p.val && root.val > q.val) root = root.left;
while (root.val < p.val && root.val < q.val) root = root.right;
return root;
}
}
``````

• @FanChen

NOTE: I WILL SWAP THESE 2 LINES TO JUST USE THE EXAMPLE PROVIDED

``````       while (root.val > p.val && root.val > q.val) root = root.left;
while (root.val < p.val && root.val < q.val) root = root.right;
``````

After Swapping

``````       while (root.val < p.val && root.val < q.val) root = root.right;
while (root.val > p.val && root.val > q.val) root = root.left;
``````

What is happening is that you need to repeat these 2 till the time you don't find the actual solution.

``````        _______6______
/              \
___2__          ___8__
/      \        /      \
0      _4       7       9
/  \
3   5
``````

6 is the root and let's say you need to find the LCA of 3 and 5
Now 6 > 3 and 6 > 5.... therefore 6 remains 6 (first while loop ends)

1. Now the second condition is to check if 6 > 3 and 6 > 5 (2nd while) we see that this is satisfied. 6 => 2
So it will give 2 as the answer --- > but the real answer is 4

OK, so what happened? Your code is good but will fail for some test cases because logically swapping the 2 while statements should have given the correct solution in the first place. Which you see here it does not.

So what I tried is

while(true) {

if(root.val >= p.val && root.val <= q.val) break;
while 1
while 2
}

but this gives another error -> there is no guarantee that p < q
So, would recommend you to use the solution provided already. It's clean.

But I hope you realized why the 2 while logic in not working :)

• ``````public class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
int min=Math.min(p.val,q.val);
int max=p.val+q.val-min;
while(!(root.val>=min&&root.val<=max)){
if(root.val>max) root=root.left;
if(root.val<min) root=root.right;
}
return root;
}
}`````````

• @majun8cn I think that in the problem it says "....of two given nodes IN THE BST", and this means both p and q are in the tree for sure. So they didn't build any testcases with the invaild input you mentioned.

• @ofLucas Thank u so much for your code! I had the same doubt about duplicates and the same idea using markings to indicate what we have found so far. Below is your code, and I just add some explanations:

``````public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
TreeNode[] ans = new TreeNode[1];
/* the author used ans[0] cuz java do not support pass by reference;
* could we use TreeNode ans = null? No! Even though when it comes to objects,
* java uses pass by value of the (pointers to the memory address), we could not change
* the "content" in the memory address using ans = r in the recursive functions,
* since ans is just a "copy"(pass by value) of a pointer to ans, and we only change
* that copied pointer to r, the ans in the original function has not been changed!
* notice that if p or q is not in the BST, ans could be null;
* */
lca(Integer.MIN_VALUE, Integer.MAX_VALUE, root, p, q, ans);
return ans[0];
}

private int lca(int bot, int top, TreeNode r, TreeNode p, TreeNode q, TreeNode[] ans) {
//is p or q possibly there?
if (r == null) return 0;
if ((p.val > top || p.val < bot) && (q.val > top || q.val < bot)) return 0;
//this is the same idea as mine, to use n to mark
//whether we've found: (p or q) n=1; or (p and q) n=2;
int found1 = lca(bot, r.val, r.left, p, q, ans), found2 = lca(r.val, top, r.right, p, q, ans);
if (found1 > 1 || found2 > 1) return 2;//we do not rewrite ans[0] cuz n>2 indicates that we have already found them!
int found = found1 + found2 + ((r == p || r == q) ? 1 : 0);
if (found > 1) ans[0] = r;
return found;
}``````

• @fanofxiaofeng I don't understand why "while(true)" works but "while(root != null) doesn't work. can you please explain this?

• @jingzhetian yes,good solution,you plenty use the features of BST,thx :)

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