Lang: C++, Complexity[Time,Space]: [O(n), O(height)]


#1

The idea is find recursively the element if found return back while storing the elements on the way back to root these are ancestors. Do it for both the given numbers and then compare their ancestors in linear time.

void getAncestors(TreeNode* A, int B, stack<int> &s)
{
    if(A==NULL)
        return;
    if(A->val == B)
        s.push(A->val);
    else
    {
        getAncestors(A->left, B, s);
        if(!s.empty())
        {
            s.push(A->val);
            return;
        }
        getAncestors(A->right, B, s);
        if(!s.empty())
        {
            s.push(A->val);
            return;
        }
    }
}
int Solution::lca(TreeNode* A, int B, int C) 
{
    int ans=-1;
    stack<int> sB,sC;
    getAncestors(A, B, sB);
    getAncestors(A, C, sC);
    
    if(sB.empty() || sC.empty())
        return ans;
    
    else if(sB.size()==1 || sC.size()==1)
        return A->val;
        
    else
    {
        while(!sB.empty() && !sC.empty())
        {
            if(sB.top() == sC.top())
                ans=sB.top();
            else
                return ans;
            
            sB.pop(); sC.pop();
        }
    }
    return ans;
}