The distance between each pair of nodes in the tree

Question

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

Answer 1

As I mentioned in the commentary, considering that the output should be (v1,v2,distance) for each pair of vertices v1,v2 in your tree - note that there is a pair of n*(n-1) such vertices. Since n*(n-1) is in O(n^2) - and this is the size of the output, it cannot be executed better than O(n^2) , so your algorithm is optimal in terms of a large O record.

Answer 2

If you want to be able to respond to distance(u, v) form requests quickly enough with quick preprocessing, you can use LCA . An LCA, or the lowest common ancestor, of the two vertices in the root tree is the vertex that is their ancestor of both, and which is the lowest among all their common ancestors. There is a not very complicated algorithm for searching LCA(u, v) in logarithmic time with n log n preprocessing time. I can describe it if necessary.

So, your problem can be solved as follows. First fix the root of your tree. Then do the above preprocessing to be able to find the LCA. Then, assuming that h[v] is the distance from v to the root (can be pre-calculated in linear time for all vertices), then distance(u, v) = h[u] + h[v] - 2 * h[LCA(u, v)] .