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

// 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.