Distance between every pair of nodes in a tree

Question

Given A Tree. How to find distance between every pair of nodes in tree without using 2D matrix of size n*n. I know solution of O(n^2) complexity .

Answer 1

If you want to be able to answer queries of form distance(u, v) fast enough with fast preprocessing, you may use LCA. LCA, or lowest common ancestor, of two vertices in a rooted tree is a vertex which is an ancestor of both of them and which is the lowest among all of theirs common ancestors. There is a not very complex algorithm to find LCA(u, v) in logarithmic time with n log n preprocessing time. I can describe it if it is needed.

So, your problem may be solved as following. First, fix a root of your tree. Then make an above mentioned preprocessing to be able to find LCA. Then, supposing h[v] is a distance from v to the root (can be precomputed in linear time for all vertices) then distance(u, v) = h[u] + h[v] - 2 * h[LCA(u, v)].