Easy C++ Solution using Backtracking


#1

Time Complexity = O(h^2) Space Complexity = O(h) where h is the height of a tree.
` bool Solve(TreeNode* A, int tar, vector& arr){
if(A==NULL)
return false;
if((*A).val==tar){
arr.push_back((*A).val);
return true;
}
arr.push_back((*A).val);
bool flag1=Solve((*A).left, tar, arr);
bool flag2=Solve((*A).right, tar, arr);
if(flag1 || flag2)
return true;
arr.pop_back();
return false;
}

int Solution::lca(TreeNode* A, int B, int C) {
    int i, j;
    vector<int> a1={};
    vector<int> a2={};
    Solve(A, B, a1);
    Solve(A, C, a2);
    for(i=a1.size()-1; i>=0; i--){
        for(j=a2.size()-1; j>=0; j--){
            if(a1[i]==a2[j])
                return a1[i];
        }
    }
    return -1;
}`