How to find the most SUITABLE root for a given tree?

general
, ,
1

Hi,

There are a number of problems involving trees in which we have to find LCA, distances etc. Such problems require that a node is assigned as a root node of the tree.

Like in case of LCA-

Dist(a,b) = Dist(a,root) + Dist(b,root) - 2*Dist(LCA(a,b), root)

Are there any known, good methods for finding out the most optimal root for the tree(As any node can be considered as a root).

Thanks

1 Like
2

No one? …okayyy :frowning:

3

It’s only a heuristics, but we had a problem here on CodeChef, and subrpoblem was to find longest path in tree (just two DFSs) I would choose the node at the middle of the longest path…

4

I suppose the best choice would be the node that minimizes the depth of the tree, called the centroid.

It can be found easily using BFS - you remove leaves of the tree one by one, and if you find out that the parent of the leaf you just removed (there’s just one such node, so we could call it a parent) becomes a leaf now, you add it to the BFS queue. The last node left is the centroid.

3 Likes