bool is_present(TreeNode* node, int x, vector<TreeNode*>& path){
if(node==NULL)
return 0;
else{
if(node->val==x){
path.push_back(node);
return 1;
}
else{
bool left = is_present(node->left,x,path);
bool right = is_present(node->right,x,path);
if(left or right){
path.push_back(node);
return 1;
}
else
return 0;
}
}
}
TreeNode* common_ancestor(vector<TreeNode*>&path1,vector<TreeNode*>&path2){
int i=path1.size()-1;
int j=path2.size()-1;
while(i>=0 and j>=0 and path1[i]->val==path2[j]->val){
i--;j--;
}
i++;
return path1[i];
}
TreeNode* least_common_ancestor(TreeNode* root,int val1, int val2){
if((root->val == val1) or (root->val == val2))
return root;
vector<TreeNode*> path1,path2;
bool is_left_val = is_present(root->left,val1,path1) and is_present(root->left,val2,path2);
if(is_left_val==1){
return common_ancestor(path1,path2);
}
path1.clear();
path2.clear();
bool is_right_val = is_present(root->right,val1,path1) and is_present(root->right,val2,path2);
if(is_right_val==1){
return common_ancestor(path1,path2);
}
return root;
}
int Solution::lca(TreeNode* A, int B, int C) {
vector<TreeNode*>temp;
if(is_present(A,B,temp) and is_present(A,C,temp)){
TreeNode* soln = least_common_ancestor(A,B,C);
return soln->val;
}
return -1;
}