## How to find the 'central node' of a tree?

Moderator: Board moderators

saatvik
New poster
Posts: 3
Joined: Thu Jul 28, 2005 3:22 pm

### How to find the 'central node' of a tree?

Hi,

I was hoping somebody could explain me an algorithm to find the 'central node' of a tree, i.e. - the node from which the maximum distance to any other vertex is minimized over all vertices.

Thank You

Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong
Identify the longest path of the tree. Then it's median node is the central node.

To identify the longest path, apply dfs from any node. Pick one of the deepest node from the dfs tree. Apply dfs again from this node. The path from this node to the deepest node of the second dfs tree is the longest path.

sharpobject
New poster
Posts: 4
Joined: Sun Jul 31, 2005 6:37 am
Contact:
The first solution that comes to mind is to run Floyd-Warshall on the graph, then search for the optimal node. Almost as soon as I started typing that, I realized it sucked. So instead, I made up another algorithm and realized 20 minutes later it was broken. Sorry.

Floyd-Warshall takes O(n^3) time and O(n^2) space in the number of nodes when coded correctly.

Edit: Cho owns me

Cosmin.ro
Learning poster
Posts: 95
Joined: Thu Aug 21, 2003 12:02 am
You can at the first step eliminate all the leaves of a tree, doing so decreases the largest distance by 1. We repeat this until one or two nodes remain, these will be the nodes with the largest distance to other nodes. You can use this algoritm to find the center of the tree in O(n).

saatvik
New poster
Posts: 3
Joined: Thu Jul 28, 2005 3:22 pm
Cosmin - Does your solution work on weighted trees?
Cho - I didn't really understand why the algo you suggested works.

Thanks

Cosmin.ro
Learning poster
Posts: 95
Joined: Thu Aug 21, 2003 12:02 am
No my algorithm doesn't work on weighted trees. For weighted trees you could try something like this: add another node and join every leaf with this node and the weigth of each added edge will be 0. Now just apply the Dijkstra algorithm with heaps and the node that is farthest away from the new node will be the center. So the algoritm will be O(M log N) but the number of edges is O(M) so we have a O(N log N) solution.