How do you find the lowest common ancestor of two nodes in a binary tree?
You walk down the tree and look for the first node that is an ancestor of both of the nodes you were given. That node is the answer.
the tree 8
/ \
3 10
/ \ \
1 6 14
the lowest common ancestor of 1 and 6 is 3
And the key idea is the word "lowest". The ancestor has to be the one that is deepest in the tree, because there is always more than one node that is an ancestor of both. The root is always an ancestor of both, so the root is never the answer unless the two nodes are in different sides of the root.
And there are three cases to think about.
The first case is that the two nodes are in different sub-trees of a node. Then that node is the answer, because it is the deepest node that has both of them underneath it.
The second case is that one of the nodes is the answer itself. That happens when one of them is an ancestor of the other. Then the ancestor is the lowest common ancestor.
The third case is that both nodes are in the same sub-tree. Then you keep going down into that sub-tree, because the answer is somewhere below the current node.
And how do you find them? The simplest way is to write a function that says whether a node is in the tree, and then you check the left side and the right side of each node.
at each node
the left has node one? the right has node two?
yes and no the answer is this node
no and yes the answer is this node
yes and yes go down into the left side
no and no go down into the right side
So the rule to remember is this. The answer is the deepest node that has both of the given nodes underneath it.
The next two questions in this topic show the code for the general case and for the special case.