Tags: , | Posted by Admin on 1/16/2012 5:32 PM | Comments (0)

Question: How to find the Least Common Ancestor for 2 nodes of a binary tree?

This sounds like "On finding lowest common ancestors: simplification and parallelization", by Baruch Schieber and Uzi Vishkin, SIAM J. Comput. Vol 17, No 6, December 1988. A google search leads me tohttp://ia700208.us.archive.org/12/items/onfindinglowe00schi/onfindinglowe00schi.pdf.

I actually wrote an implementation of this for fun - it is in a zip file miscellaneous for-fun Java code that you can find off a link from http://www.mcdowella.demon.co.uk/programs.html.

(The algorithm needs linear space and time for pre-processing, then runs at O(1) per query).

Comments are closed