# Solution of LCA with handling each edge case separately with explanations

Tags: #<Tag:0x00007f18201a3d28>

#1

#include<bits/stdc++.h>
/**

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

// Finds the path from root node to given root of the tree, Stores the
// path in a vector path[], returns true if path exists otherwise false
bool traversal(TreeNode *root ,int value, vector &v )
{
//BASE CASE
if( root == NULL ) return false;

``````// Store this node in path vector. The node will be removed if
// not in path from root to k
v.push_back(root->val);

// See if the value is same as root's key
if( root->val == value )    return true;

// Check if k is found in left or right sub-tree
if(traversal(root->left  , value , v ) || traversal(root->right , value , v ) )   return true;

// If not present in subtree rooted with root, remove root from
// path[] and return false
v.pop_back();
return false;
``````

}

// Returns LCA if node n1, n2 are present in the given binary tree,
// otherwise return -1
int Solution::lca(TreeNode* root, int p, int q)
{
if( root == NULL ) return -1;//BASE CONDâ€™n

``````// to store paths to p and q from the root
vector<int>v1,v2;

// Find paths from root to p and root to q. If either p or q is not present, return -1.
if( !traversal( root , p , v1 ) || !traversal( root , q , v2 ) )  return -1;

//If both element are same then youngest CA is the value itself.
if( p == q )                                                      return  p;
int i = 0;

/* Compare the paths to get the first different value */
while( i < v1.size() && i < v2.size() )
{
if( v2[i] != v1[i] )     return v1[i-1];
else if( v2[i] == v1[i] && ( v1[i] == p || v1[i] == q ) )   return v1[i];//if one node one of the lca of another node.

i++;
}
``````

}