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];
}