Lowest Common Ancestor of a Binary Tree
An ancestor of a node is a node that occurs along the root to till the node. So, all the nodes that occur along the root to node path can be called as an ancestor. Also, we consider a node to be an ancestor of itself.
Now, the problem statement is that given two nodes, there will be multiple ancestors that are common to either node. Our task is to find the lowest among them (positionally).
Few example :
The lowest common ancestor of 5,1 is 3. The LCA of 6,4 is 5.
An approach that comes to mind is to traverse the tree until you meet the target node, store all the nodes encountered so far, in a list called ancestors, for both node1 and node2.
Eg — Ancestors of 2 = [3,5,2]
Ancestors of 6 = [3,5,6]
Answer = 5
Then we can traverse the array simultaneously, and the last element that is common is the LCA. Here it is 5.
The moment we encounter an element that is unequal in either ancestor, we break. The result will be i-1th element, because that was the last equal element.
Optimized Approach
We should not be using extra space. Use a bottom up approach.
The basic idea is, if we have got the LCA in any of the subtrees, then from there we would be getting the LCA returned. So, the other subtree would definitely return NULL.
Also, if this root is a target, means it is definitely the LCA so far.
So, if both are null, return NULL. (Unless the root is the target itself)
But, if onlyone of the subtree is null, then the LCA has been obtained in the other tree, so return that.
And lastly, if both are non-null, means LCA is coming from both subtrees, which is not possible, which actually means, the current root is the LCA.
( Because, if from both subtrees some value is coming, it means they are returning the target each)
Another way of writing this logic :
Here we see if both left and right subtree are returning a target each, it means the LCA is the root.
But if one of them is NULL, and the other returns something, we have to transmit it to preserve the information.