Binary Search Tree : Lowest Common Ancestor

  • + 1 comment

    Two things:
    The first: The problem never tells us in the constraints that v1 < v2, that's an assumption that happens to be true this time.

    If you did make that assumption, why this code:

    if(root.data < v1 && root.data < v2){
        return lca(root.right,v1,v2);
    }
    //Bigger than both
    if(root.data > v1 && root.data > v2){
        return lca(root.left,v1,v2);
    }
    

    If you are assuming v1 < v2, then if root.data < v1, root.data cannot possibly >= v2.

    My code uses this tautology do its advantage by only checking what is necessary to determine what we need to know. Therefore, it is better than your code, because it uses x/2 + 1 comparisons, where x is the number of comparisons you make, and I maintain that you should check beforehand, because the check itself can only have a marginal cost but since the whole algorithm relies on it, you shouldn't simply trust that whoever uses your code is going to follow your rules.

    • + 0 comments

      i made throw(exception) assumption is wrong swapping everything in the beginning simplifies problem significantly