Find the first common ancestor of two nodes in a binary tree
- Create two arrays with in-order and post-order traversal for the given binary tree and call them in-order and post-order traversal respectively.
- Find the number of nodes in-between the given two nodes in the in-order traversal and call it middleNodes.
- Find the index of each element in the middleNodes array with respect in the post-order traversal array.
- Return the node with the highest index.
- Running time O(n)
Watch the following excellent video to understand this algorithm in more detail!