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


  • 3
    W

    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?


  • 0
    Q

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

  • 0
    T

    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.


Log in to reply
 

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