Modified Lowest Common Ancestor | CODING INTERVIEW ARCHIVES

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.

Read full article from Modified Lowest Common Ancestor | CODING INTERVIEW ARCHIVES