Lowest Common Ancestor- Code Explain

Question

LCA by inorder and postorder traversal was easily implemented and understood by me.

But, there is a recursive bottom-up approach.

I had a look at the code online, and I didn't understand one line:

Here is the code:

public Node lowestCommonAncestor(int val1, int val2,Node root){
    if(root == null){
        return null;
    }
    if(root.data == val1 || root.data == val2){
        return root;
    }

    Node left = lowestCommonAncestor(val1, val2, root.left);
    Node right = lowestCommonAncestor(val1, val2, root.right);

    if(left != null && right != null){
        return root;
    }
    return left != null ? left : right;
}

val1 and val2 are two node's value whose LCA needs to be found.

The last line is where I am stuck on.

return left != null ? left : right;

Can some one explain this?

Thank you.

Answer 1

This is(kind of) neat implementation of the naive approach, but implemented top-to-bottom instead of the standard bottom-to-top. Let's try to analyze what does lowestCommonAncestor(int val1, int val2,Node root) return.

left will be not null if at least one of val1 and val2 is found in the left subtree of root. Analogously right will be not null if and only if least one of val1 and val2 is found in the right subtree of root. Apparently the if statement if(left != null && right != null){ will be true if and only if precisely one of val1 and val2 is found in the left subtree and precisely one of val1 and val2 is found in the right subtree. Thus this will happen only for the lowest common ancestor of val1 and val2(draw a picture if you need to). For this node, the root will returned. For all other nodes, the function will return the lowestCommonAncestor in the left or in the right subtree depending on which one is not null or null if both are null.

So for all nodes above the LCA, precisely one of right and left will be not null(as val1 and val2 will be in one of the subtrees) and that would be the root of the subtree where the LCA is. As a consequence the return value of the call of lowestCommonAncestor for all nodes above the LCA will be the LCA itself. As a conequence the call on the root of the original tree will really be the LCA.

Answer 2

// Method to find lowest common ancestor.
public Node lowestCommonAncestor(int val1, int val2,Node root){

    // Base condition to terminate.
    if(root == null){
        return null;
    }

    // While traversing, if we found root itself equal to val1/val2.
    // Then, root should be the lowest common ancestor.
    if(root.data == val1 || root.data == val2){
        return root;
    }

    // If not, do post-order traversing. Means, left node, then right 
    // node, then root iteslf (current node.)
    Node left = lowestCommonAncestor(val1, val2, root.left);
    Node right = lowestCommonAncestor(val1, val2, root.right);

    // While traversing, if we reach to a state, when root itself has left and 
    // right both children, then, this is the lowest common ancestor of val1, 
    // and val2. return this root.
    if(left != null && right != null){
        return root;
    }

    // If, root has only one child either  left or right child, then start 
    // traversing into that child.
    // If, root has no child, in that case. Return null. Means this tree does    
    // not contain lowest common ancestor of val1, and val2.
    return left != null ? left : right;
}

I explained the whole code by putting comments. I think that will make more sense. Please go through it. If you still have any doubt, feel free to ask.