C++ lengthy code but easy to understand with proper comments


#1

void inorder(TreeNode*A,int B,int C,bool &flag1,bool &flag2){
if(A==NULL){
return;
}
if(A->val==B){
flag1=true;
}
if(A->val==C){
flag2=true;
}

 inorder(A->left,B,C,flag1,flag2);
 inorder(A->right,B,C, flag1,flag2);
 
 return;

}

void findpath(TreeNode* A,int B, vector curr,bool &flag,vector &ans){
if(A==NULL){
return;
}
if(flag){
return;
}
curr.push_back(A->val);
if(A->val==B){
flag=true;
ans=curr;
return;
}

 findpath(A->left,B,curr,flag,ans);
 findpath(A->right,B,curr,flag,ans);
 
 return;

}

int Solution::lca(TreeNode* A, int B, int C) {
bool flag1=false;
bool flag2=false;
// inorder traversal to find whether B and C exist in the Tree
inorder(A,B,C,flag1,flag2);

if(!flag1 || !flag2){
    return -1;
}

if(B==C){
    return B;
}
vector<int> v1;
vector<int > v2;
vector<int> ans1;
vector<int> ans2;

flag1=false;
flag2=false;

// It will give path of the Node B
// this is same as path to Given Node(InterviewBit Question)
findpath(A,B,v1,flag1,ans1);
// It will give path of the Node B
findpath(A,C,v2,flag2,ans2);
int i=0;
int j=0;
int res1=0;
int res2=0;

while(i<ans1.size() && j<ans2.size() && ans1[i]==ans2[j]){
    res1=i;
    res2=j;
    i++;
    j++;
}

// we can return ans2[res2] also
return ans1[res1];

}