Lowest Common Ancestor of a Binary Search Tree - Depth First Search / Binary Search Tree

Problems
21

I think it should also be noted in the problem that p and q are guaranteed to be in the tree. In general, I think this more general case should be presented. It’s obviously up to us to clarify with interviewer, but if they say p/q aren’t guaranteed to be in tree, then most folks won’t know how to do that based on the current solution.

1 Like
23

Maybe this is simpler to understand,

public static List<Integer> getPath(Node<Integer> bst, int val, ArrayList<Integer> res){
    if(bst == null){
        return new ArrayList<Integer>();
    }
    else if(bst.val == val){
        res.add(bst.val);
        return res;
    }
    else if(bst.val< val){
        res.add(bst.val);
        return getPath(bst.right,val,res);
    }
    else{
        res.add(bst.val);
        return getPath(bst.left,val,res);
    }
}

public static Integer lcaOnBst(Node<Integer> bst, int p, int q) {
    // WRITE YOUR BRILLIANT CODE HERE
    // do path of p , path of q
    // logn + logn
    // find the common ones, and take the least? (N, where N=  O(2 * height of tree))
    
    List<Integer> pathp=getPath(bst, p,new ArrayList<Integer>());
    List<Integer> pathq=getPath(bst,q,new ArrayList<Integer>());
    
    // find the min common, least common integer/parent
    if(pathp.isEmpty() || pathq.isEmpty()){
        return null;
    }

    List<Integer> commonAncesters=new ArrayList<Integer>();
    pathp.retainAll(pathq);
    Integer answer=pathp.get(0);
    for(Integer i: pathp){
        answer=(int)Math.min(i, answer);
    }
    return answer;
}

lemme know

24

My suboptimal solution with the same time and space complexity

def lca_on_bst(bst: Node, p: int, q: int) -> int:
    def search(node, val, path):
        if not node:
            return False

        path.append(node.val)
        if val < node.val:
            return search(node.left, val, path)
        elif val > node.val:
            return search(node.right, val, path)
        else:
            return True
    
    path_p = []
    path_q = []
    search(bst, p, path_p)
    search(bst, q, path_q)
    prev_common_ancestor = None
    min_length = min(len(path_p), len(path_q))
    for i in range(min_length):
        if path_p[i] != path_q[i]:
            break
        prev_common_ancestor = path_p[i]

    return prev_common_ancestor
25

I think that this problem should explicitly state that it is a precondition that the values p and q are represented by nodes in the BST.

While I think it may be implicitly understood - the solution requires traversal all the way down to both values to ensure that they exist in the BST if we aren’t granted with certainty that they are in there.

26

A simpler one and clarity is:

def lca_on_bst(bst,p,q):
  
 if not bst:
     return bst
# If either p or q is found, return the node
 if bst.val==p or bst.val==q:
    return bst.val
 # Recursively search for LCA in the left and right subtrees
 left_LCA=lca_on_bst(bst.left,p,q)
 right_LCA=lca_on_bst(bst.right,p,q)
 
# If both p and q are found in different subtrees, return the current node as LCA
 if left_LCA and right_LCA:
    return bst.val

# If one of p or q is found, return that node; otherwise, return the other found LCA
 return left_LCA if left_LCA else right_LCA
27

there is no enough test cases.
for example the following code passes all test cases, even though it is incorrect

        if p < bst.val and q < bst.val:
            return dfs(bst.left, p, q)

        
        return bst.val