Solution of LCA with handling each edge case separately with explanations

interview-questions
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++;
}

}