Lowest Common Ancestor - Depth First Search / Advanced

Problems
31

This has got to be my favourite explanation so far! wow!

32

Careful, this solution assumes that it is a BST and not just a Binary Tree. I originally wrote my solution like that until I re-read through the problem and realized this was for a Binary Tree.

34

Here is a intuitive solution i suppose, I just modified my the previous problem approach,

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

public static Node lcaOnBst(Node bst, Node p, Node 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<Node> pathp=getPath(bst, p,new ArrayList<Node>());
    List<Node> pathq=getPath(bst,q,new ArrayList<Node>());
    
    // find the min common, least common integer/parent
    if(pathp.isEmpty() || pathq.isEmpty()){
        return null;
    }

    List<Node> commonAncesters=new ArrayList<Node>();
    pathp.retainAll(pathq);
    Node answer=pathp.get(0);
    for(Node i: pathp){
        if(i.val < answer.val){
            answer=i;
        }
    }
    return answer;
}

public static Node lca(Node root, Node node1, Node node2) {
    // WRITE YOUR BRILLIANT CODE HERE
    return lcaOnBst(root, node1,node2);
}

lemme know

35

This is my code. I’m passing Test Cases 1, 2, and 4, but failing test case 3. Not sure why! I used the same logic as the solution.
Help would be appreciated. Thanks!

Node<int>* lca(Node<int>* root, Node<int>* node1, Node<int>* node2) {
    if (root == nullptr) {
        return nullptr;
    }
    if (root->val == node1->val) {
        return root;
    }
    if (root->val == node2->val) {
        return root;
    }
    Node<int>* valL = lca(root->left, node1, node2);
    Node<int>* valR = lca(root->right, node1, node2);
    if (valL != nullptr && valR != nullptr) {
        return root;
    } else if (valL != nullptr) {
        return node1;
    } else if (valR != nullptr) {
        return node2;
    } else {
        return nullptr;
    }
}
36

Ok I don’t understand how nobody seems to have noticed this…
None of the solutions even look at the values of the nodes. For example if you are looking for the LCA of [3,5], NONE of these solutions even take in these values as input.

37

I am just curious, is there going to be any speed runs for these topics, BFS DFS etc I have seen most of these topics are missing speed runs for them.