Lowest Common Ancestor in a Binary Tree for noobs like me.

Source to the problem: https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/submissions/

What is the meaning of an ancestor of a Node?

Simple, the parent,grand parent,great grand parent so on and so forth recursively, are the ancestors of a node.

Ancestor of 4

Example the ancestors of4 are2,5 and 3. While for 5 it is 3.

If you observe carefully, you can see that, to reach a node, you need to actually traverse through the ancestors of the node.

This observation is very important.

So to find the common ancestors of two nodes, we need to first find the ancestors of the two nodes, and then find the lowest common ancestors.

What does “lowest” in lowestcommon ancestor mean?

Here the term “lower” can be in terms of the “level” or “depth” of the tree. For example, I have marked the level of each node of the tree below:

level of a tree

Hence the lowest “level” is 4, followed by 3, 2 and 1.

So to find the LCA(lowest common ancestor), we need to find the path leading to each of the nodes and find the lowest common node in them.

Suppose we need to find LCA of nodes 4 and 8. Here we get the paths as:

3,5,2,4 and 3,1,8. But now, how do we find the lowest common node in the 2 lists? We could intelligently use 2 pointers approach, starting from the end of both the arrays, and stop when we find the first common node. Since we are doing from the end, we would find the lowest common node for sure.

To allow us to use 2 pointers, while storing the path, we store the level of each node too. Example:

[ (3,1), (5,2), (2,3), (4,4) ] and [ (3,1), (1,2), (8,3) ] .

Now, we can start from the end of both the arrays find the common node using the code:

finding common ancestor

Here path1 and path2 are lists of tuples, where each tuple is of the format: <TreeNode,level>.

The Logic is that until we find a common node(which the question guarantees), we see if the two nodes are of the same level, if so, we skip both the nodes. If not, then we move the pointer pointing to the node with larger level forward.

example

As we can see above, the path of node1 and node2 are shown. The common ancestor cannot be at levels greater than that of min(level_3,level_4)=level_3. Hence we move the pointer of array1 until the levels are same or lesser than that of the pointer to array2. Rest of the iteration is shown below:

same level,skip both the nodes

Same level,skip both the nodes

while loop breaks since the node_values aresame

When the while loop is broken, we have pointer to the common ancestor. Here is the final code:

python code