O(n) solution with just once traversal


#1

public class Solution {

int ans = -1;

public boolean findN(TreeNode node, int B, int C)
{
    
    if(ans != -1)
        return false;
    if(node == null)
        return false;
    
    boolean left = findN(node.left, B, C);
    boolean right = findN(node.right, B, C);
    if(node.val == B || node.val == C)
    {
        if(B == C)
        {
            ans = node.val;
            return true;
        }
        if(left || right)
        {
            ans = node.val;
            return true;
        }
        return true;
    }
    if(left && right)
    {
        ans = node.val;
        return true;
    }
    return left || right;
}

public int lca(TreeNode A, int B, int C) {
    
    findN(A, B, C);
    return ans;
    
}

}