• 0

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!