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;
}
}
}
My Java Solution


A nonrecursive 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; } } }


@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)
Your program will return root instead of correct answer.
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.

Hi why is the nonrecursive 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; } }

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) 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 :)
 Now the second condition is to check if 6 > 3 and 6 > 5 (2nd while) we see that this is satisfied. 6 => 2

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.valmin; 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?
