|Presentation for Open Source Project: lcalibrary|
Now that we have determined the calculation of LCA is useful, we can consider a trivial solution.
For all nodes in the tree, create a table that stores the LCA of any two nodes. So we simple calculate the LCA(X,Y) where X and Y are all the possible LCA queries based upon the tree.
This works fine, but is dreadfully slow. Supposing that our data set is huge, this would be quite tedious, in fact it is O(n^3).
Copyright 2003, Zack Ramjan