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

Lowest-Common-Ancestor-Example-1

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)

Watch the following excellent video to understand this algorithm in more detail!

Solution


You may also like...

Leave a Reply

Your email address will not be published. Required fields are marked *

Show Buttons
Hide Buttons