### Nearest Common Ancestors

Posted:

**Sat Jun 29, 2013 10:36 pm**Problem: http://poj.org/problem?id=1330

My solution got

I am not able to figure out what I can do to imporve the solution.

My solution:

First read all the edges and keep making the tree i.e. after reading each input line assign the parent,child pointer.

Then for each of the two nodes for which we have to find out the nearest common ancestor:

Keep putting into vector its ancestor one by one till we reach the root.

Then to find out the nearest common ancestor, keep iterating the two vectors in a reverse iteration till the corresponding elements are same.

This should be O(n) time complexity.

Since we would be given only two nodes in the tree to compute nearest common ancestor, I didn't tried http://community.topcoder.com/tc?module ... onAncestor

Can anyone suggest what I can improve for my solution to get accepted?

Regards,

Kaushik

My solution got

**Time Limit Exceeded**.I am not able to figure out what I can do to imporve the solution.

My solution:

First read all the edges and keep making the tree i.e. after reading each input line assign the parent,child pointer.

Then for each of the two nodes for which we have to find out the nearest common ancestor:

Keep putting into vector its ancestor one by one till we reach the root.

Then to find out the nearest common ancestor, keep iterating the two vectors in a reverse iteration till the corresponding elements are same.

This should be O(n) time complexity.

Since we would be given only two nodes in the tree to compute nearest common ancestor, I didn't tried http://community.topcoder.com/tc?module ... onAncestor

Can anyone suggest what I can improve for my solution to get accepted?

Regards,

Kaushik