Find the first common ancestor of two nodes in a binary tree

Algorithm

• 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)

Solution