Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Share On Reddit
Contact us
Hide Buttons

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 *