# O(lgn) solution. But, what for BST with duplicate values?

• Below is my clean Java solution that assumes following definition of BST:-

left < root < right

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

Now, my question:-

Many definitions of BST is like following (one that allows duplicate values) :-

left <= root < right. This too is a valid BST.

However, the solution above will fail with this definition of BST. Below is the counter example :-

2
/
2
/
2

If p and q are 2's on level 1 and level 2, above solution will return root (i.e. node at level 0) as result. However, actual answer is the one at level 1. How to deal with this situation?

• I think the most commonly accepted definition is that keys in BST must be unique.
For your case (left <= root < right) the solution will be. Strange that you could solve unique BST but not this case...

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

• It is a Binary "Search" Tree. All nodes by rule represent unique keys meant for searching. That is why, it would not make sense for the BST to have multiple same-valued keys. Having duplicate keys defeats the whole purpose of a Search tree. You're probably confused between a BST and a plain Binary Tree. A similar problem for Binary Tree can be found here:
https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/

Hope that makes sense.

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