Given a connected, undirected, acyclic graph with N nodes, how can I find the height of every tree spanning all nodes in the graph in linear time?
1 Answers
1
votes
Rephrased: given an unrooted tree T, compute, for each vertex v of T, the height of the rooted tree T(v) derived from T by rooting it at v.
First choose an arbitrary root r for T, yielding T(r). Scan T(r) leaves-to-root, storing, for each vertex v, the height of the subtree of T(r) rooted at v. Scan T(r) root-to-leaves, computing, for each vertex v, the length of the longest path in T from v that does not visit a proper descendant of v (with respect to T(r)). This second step is slightly trickier; you need to compute the greatest and the second greatest of the heights of v and its siblings, which can be reused for v's siblings. The height of T(v) is the maximum of its two labels.
