Modified Lowest Common Ancestor | CODING INTERVIEW ARCHIVES
The lowest common ancestor(LCA) between two nodes a and b is defined as the lowest node in tree T that has both a and b as descendants (where we allow a node to be a descendant of itself).
The problem here is to find the LCA of 2 nodes, in such a way that a given node is not allowed to be a descendant of itself. Hence, if any of the 2 nodes is the root of the tree then the LCA does not exist.
Approach:
To find the LCA, we follow a recursive approach. If the root has value equal to any of a or b, we return the root.
We recursively find the nodes in the left subtree and the right subtree.
If both the subtree respectively have 1 of the 2 given nodes, we return the root.
Else, if any one of the 2 return values is not NULL, return that value (It means atleast 1 of the nodes is found in that tree).
Else, return NULL (It means none of the 2 nodes is found in the subtrees).
The base case is to return NULL for a NULL root.
Now, for the modified LCA problem, instead of checking the value of root to be equal to one of the given values a or b, we check if any of the value a or b is equal to the value of any of the 2 child of root node.
This is done only if the corresponding child of the root exists. Thus, the base case can be to return NULL if none of the child exists(i.e. the root is a leaf).
Other conditions and the code remains the same.
// Function to build a sample tree from given
// inorder and preorder traversals
Node treeFromInAndPre(int *in,int *pre,int lb,int ub,int *idx){
if(lb>ub)
return NULL;
int i=lb;
while(in[i]!=pre[*idx])
i++;
Node root=getNode(pre[*idx]);
(*idx)++;
root->left=treeFromInAndPre(in,pre,lb,i-1,idx);
root->right=treeFromInAndPre(in,pre,i+1,ub,idx);
return root;
}
// function to get LCA
Node getLCA(Node root,int a,int b){
if(!root)
return NULL;
if(root->data==a || root->data==b)
return root;
Node left=getLCA(root->left,a,b);
Node right=getLCA(root->right,a,b);
if(left && right) return root;
else if(left) return left;
else return right;
}
// function to get LCA according to the
// modified definition
Node getLCA_Modified(Node root,int a,int b){
if(!root || root->data==a || root->data==b)
return NULL;
if(!root->left && !root->right)
return NULL;
if(root->left){
if(root->left->data == a || root->left->data == b)
return root;
}
if(root->right){
if(root->right->data == a || root->right->data == b)
return root;
}
Node left=getLCA_Modified(root->left,a,b);
Node right=getLCA_Modified(root->right,a,b);
if(left && right) return root;
else if(left) return left;
else return right;
}
Read full article from Modified Lowest Common Ancestor | CODING INTERVIEW ARCHIVES
The lowest common ancestor(LCA) between two nodes a and b is defined as the lowest node in tree T that has both a and b as descendants (where we allow a node to be a descendant of itself).
The problem here is to find the LCA of 2 nodes, in such a way that a given node is not allowed to be a descendant of itself. Hence, if any of the 2 nodes is the root of the tree then the LCA does not exist.
Approach:
To find the LCA, we follow a recursive approach. If the root has value equal to any of a or b, we return the root.
We recursively find the nodes in the left subtree and the right subtree.
If both the subtree respectively have 1 of the 2 given nodes, we return the root.
Else, if any one of the 2 return values is not NULL, return that value (It means atleast 1 of the nodes is found in that tree).
Else, return NULL (It means none of the 2 nodes is found in the subtrees).
The base case is to return NULL for a NULL root.
Now, for the modified LCA problem, instead of checking the value of root to be equal to one of the given values a or b, we check if any of the value a or b is equal to the value of any of the 2 child of root node.
This is done only if the corresponding child of the root exists. Thus, the base case can be to return NULL if none of the child exists(i.e. the root is a leaf).
Other conditions and the code remains the same.
// Function to build a sample tree from given
// inorder and preorder traversals
Node treeFromInAndPre(int *in,int *pre,int lb,int ub,int *idx){
if(lb>ub)
return NULL;
int i=lb;
while(in[i]!=pre[*idx])
i++;
Node root=getNode(pre[*idx]);
(*idx)++;
root->left=treeFromInAndPre(in,pre,lb,i-1,idx);
root->right=treeFromInAndPre(in,pre,i+1,ub,idx);
return root;
}
// function to get LCA
Node getLCA(Node root,int a,int b){
if(!root)
return NULL;
if(root->data==a || root->data==b)
return root;
Node left=getLCA(root->left,a,b);
Node right=getLCA(root->right,a,b);
if(left && right) return root;
else if(left) return left;
else return right;
}
// function to get LCA according to the
// modified definition
Node getLCA_Modified(Node root,int a,int b){
if(!root || root->data==a || root->data==b)
return NULL;
if(!root->left && !root->right)
return NULL;
if(root->left){
if(root->left->data == a || root->left->data == b)
return root;
}
if(root->right){
if(root->right->data == a || root->right->data == b)
return root;
}
Node left=getLCA_Modified(root->left,a,b);
Node right=getLCA_Modified(root->right,a,b);
if(left && right) return root;
else if(left) return left;
else return right;
}
Read full article from Modified Lowest Common Ancestor | CODING INTERVIEW ARCHIVES
