If the 'root' node has to be such that the height of the resultant tree should be minimum, then this root node must lie in the middle of the largest possible path between any 2 points in this graph.
Given above, start doing a DFS from any arbitrary node. This is doable in O(n). It will return return the heights of all its sub-trees. Pick up the top 2 heights (say a, b where a > b). The longest path now in this graph is of length a + b. The root should lie at a+b/2 from either ends, which is at distance a-(a+b/2) from the current node. Thanks, Satish On Oct 29, 6:22 pm, "Yingjie Xu" <[EMAIL PROTECTED]> wrote: > Calculate center of a tree, can be solved in O(n). > > On 10/25/07, dkrai <[EMAIL PROTECTED]> wrote: > > > > > Another approach can be to eliminate leaf nodes iteratively from tree. > > At last only root node or nodes on same level will be left. > > > Adjency list representation of graph will make it easier to > > imlplement. > > Run time cost will be O(n*n) > > > On Oct 24, 12:37 pm, "[EMAIL PROTECTED]" <[EMAIL PROTECTED]> > > wrote: > > > Two methods: > > > 1. try BFS on each vertex, calculate the longest shortest path to > > > each other vertex, compare them > > > It is easy to implement, but gives O(n*n) running time > > > > 2. divide and conquer > > > randomly divide the tree into two parts, calculate the height of > > > the two subtrees then merge them. > > > This is not so easy to implement, but really gives a good running > > > time which is O(nlogn) > > > > On Oct 21, 9:21 am, "[EMAIL PROTECTED]" <[EMAIL PROTECTED]> wrote: > > > > > Q) You are given a root-less tree (which can also be thought of as an > > > > undirected acyclic connected graph). The problem is to choose one of > > > > the nodes from the tree as root such that the height of the resultant > > > > tree is minimum. > > > > > Device an appropriate data-structure and write a program for the > > > > same. > > > > mum height possible is 2. So for this example the code should return > > > > the node '3'. > > > > > Note: All nodes are numbered from 1 to n, where 'n' is the number of > > > > nodes. Incase there are more than one roots possible, then your > > > > program can return any one of them.- Hide quoted text - > > > > - Show quoted text - --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
