My O(N) solution with comments


#1

Comment body goes here.public class Solution {

public int lca(TreeNode A, int B, int C) {
    if(null == A){
        return -1;
    }
    TreeNode lca = lcaRecurse(A, B, C);
    if(null == lca){
        // Neither B nor C is found
        return -1;
    }
    if(lca.val != B && lca.val != C){
        // If ancestor is found
        return lca.val;
    }
    if((lca.val == B && contains(lca, C)) || (lca.val == C && contains(lca, B))){
        // Case 1. One (out of B and C) is ancestor of another
        return lca.val;
    }
    // Case 2. Only one (out of B and C) is present in complete tree
    return -1;
}
private TreeNode lcaRecurse(TreeNode root, int B, int C){
    if(null == root){
        return null;
    }
    if(root.val == B || root.val == C){
        // One of them is found, no need to go further down to its substrees
        return root;
    }
    // Search left subtree
    TreeNode left = lcaRecurse(root.left, B, C);
    if(null != left && left.val != B && left.val != C){
        // If ancestor is already found in left subtree
        return left;
    }
    // Search right subtree
    TreeNode right = lcaRecurse(root.right, B, C);
    if(null != right && right.val != B && right.val != C){
        // If ancestor is already found in right subtree
        return right;
    }
    if(null != left && null != right){
        // If B and C are found on different substrees
        return root;
    }else if(null != left || null != right){
        // If B or C is found in left or right subtree
        // It can happen ifn 2 cases
        // Case 1. One (out of B and C) is ancestor of another
        // Case 2. Only one (out of B and C) is present in complete tree
        return (null != right)?right : left;
    }
    return null;
}
private boolean contains(TreeNode root, int value){
    if(null == root){
        return false;
    }
    if(root.val == value){
        return true;
    }
    return contains(root.left, value) || contains(root.right, value);
}

}