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

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

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

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

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.

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