LCA easy O(N) C++ solution


#1
    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;

}