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 -~----------~----~----~----~------~----~------~--~---
