Easy C++ solution using pre-order traversal


#1
// path function checks whether the value exists in the tree or not. Also it gives the root to that value path if the value exists in the tree
bool path(TreeNode *root,int n,vector<int>&ans)
{
    if(!root)
    {
        return false;
    }
    ans.push_back(root->val);
    if(root->val==n)
    {
        return true;
    }
    else if(path(root->left,n,ans) || path(root->right,n,ans))
    {
        return true;
    }
    ans.pop_back();
    return false;
}
int Solution::lca(TreeNode* A, int B, int C) 
{
    vector<int>v1,v2;
    if(!path(A,B,v1) || !path(A,C,v2))
    {
        return -1;
    }
    int i=0,j=0;
    while(i<v1.size() && j<v2.size())
    {
        if(v1[i]!=v2[j])
        {
            break;
        }
        i++;
        j++;
    }
    return v1[i-1];
}


#2

/**

  • Definition for binary tree
  • struct TreeNode {
  • int val;
    
  • TreeNode *left;
    
  • TreeNode *right;
    
  • TreeNode(int x) : val(x), left(NULL), right(NULL) {}
    
  • };
    */

bool Path(TreeNode* A, vector&v, int k){
if(A==NULL) return false;
v.push_back(A->val);
if (A->val == k)
return true;
// Check if k is found in left or right sub-tree
if ((Path(A->left, v, k)) || (Path(A->right, v, k)) )
return true;
// If not present in subtree rooted with root, remove root from
// path[] and return false
v.pop_back();
return false;
}
int Solution::lca(TreeNode* A, int B, int C) {
// to store paths to n1 and n2 from the root
vector path1, path2;

// Find paths from root to n1 and root to n1. If either n1 or n2
// is not present, return -1
if ( !Path(A, path1, B) || !Path(A, path2, B))
      return -1;

/* Compare the paths to get the first different value */
int i=0,j=0;
while(i<path1.size() && j<path2.size())
{
    if(path1[i]!=path2[j])
    {
        break;
    }
    i++;
    j++;
}
return path1[i-1];

}

// i have same code as of you but still it is not working