As you traverse along and find the diameter of the tree, keep track of the number of nodes thereby traversed. Let that be equal to n. Now, centre is the node corresponding to floor((n+1)/2).
On Wed, Jun 20, 2012 at 5:19 PM, Nishant Pandey < nishant.bits.me...@gmail.com> wrote: > I am asking again .. can any one please suggest better method for getting > the median on the longest path of the tree .. > efficient method . > > > On Tue, Jun 19, 2012 at 5:08 PM, Nishant Pandey < > nishant.bits.me...@gmail.com> wrote: > >> >> for getting diameter we can simply add the max height of left subtree and >> max height of the right sub tree . >> >> the main issue is how efficiently we find median on that longest path to >> get the center of the tree . >> can any bdy sugest optimized algo for that ? >> >> >> On Mon, Jun 18, 2012 at 6:08 PM, rajesh pandey < >> rajesh.pandey.i...@gmail.com> wrote: >> >>> I found it in some paper ;) >>> >>> Diameter and center >>> De nition 4. The diameter of tree is the length of the longest path. >>> De nition 5. A center is a vertex v such that the longest path from v to >>> a leaf is minimal >>> over all vertices in the tree.Tree center(s) can be found using simple >>> algorithm. >>> Algorithm 1. (Centers of tree) >>> 1: Choose a random root r. >>> 2: Find a vertex v1 | the farthest form r. >>> 3: Find a vertex v2 | the farthest form v1. >>> 4: Diameter is a length of path from v1 to v2. >>> 5: Center is a median element(s) of path from v1 to v2. >>> >>> This is O(n) algorithm. It is clear that we can't determine tree >>> isomorphism faster >>> than O(n). So, if we nd a O(f(n)) algorithm for rooted trees isomorphism >>> we can also >>> obtain O(f(n)) algorithm for ordinary trees. >>> >>> On Saturday, June 16, 2012 12:04:32 PM UTC+5:30, achala sharma wrote: >>>> >>>> I think this algorithm is used for calculating poset in graph. >>>> >>>> On Sat, Jun 16, 2012 at 3:04 AM, Hemesh Singh >>>> <hemesh.mn...@gmail.com>wrote: >>>> >>>>> + 1 for DK's solution. Is that a standard algorithm coz I feel like I >>>>> have heard it somewhere ?? >>>>> >>>>> >>>>> On Mon, Aug 8, 2011 at 1:37 AM, DK <divyekap...@gmail.com> wrote: >>>>> >>>>>> @KK: DFS and BFS are O(N) and Floyd Warshall is O(N^3). >>>>>> Could you please state how you can use the traversals directly to get >>>>>> the center? (And prove your correctness too?) >>>>>> >>>>>> The solution given by Wladimir (& expanded upon by me) is O(N) and >>>>>> uses (somewhat) the inverse of a BFS as a traversal. >>>>>> >>>>>> -- >>>>>> DK >>>>>> >>>>>> http://twitter.com/divyekapoor >>>>>> http://gplus.to/divyekapoor >>>>>> http://www.divye.in >>>>>> >>>>>> -- >>>>>> You received this message because you are subscribed to the Google >>>>>> Groups "Algorithm Geeks" group. >>>>>> To view this discussion on the web visit https://groups.google.com/d/ >>>>>> **msg/algogeeks/-/HnMOZtOrkqwJ<https://groups.google.com/d/msg/algogeeks/-/HnMOZtOrkqwJ>. >>>>>> >>>>>> >>>>>> To post to this group, send email to algogeeks@googlegroups.com. >>>>>> To unsubscribe from this group, send email to algogeeks+unsubscribe@* >>>>>> *googlegroups.com <algogeeks%2bunsubscr...@googlegroups.com>. >>>>>> For more options, visit this group at http://groups.google.com/** >>>>>> group/algogeeks?hl=en<http://groups.google.com/group/algogeeks?hl=en> >>>>>> . >>>>>> >>>>> >>>>> >>>>> >>>>> -- >>>>> Hemesh singh >>>>> >>>>> -- >>>>> 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 algogeeks+unsubscribe@** >>>>> googlegroups.com <algogeeks%2bunsubscr...@googlegroups.com>. >>>>> For more options, visit this group at http://groups.google.com/** >>>>> group/algogeeks?hl=en <http://groups.google.com/group/algogeeks?hl=en> >>>>> . >>>>> >>>> >>>> -- >>> You received this message because you are subscribed to the Google >>> Groups "Algorithm Geeks" group. >>> To view this discussion on the web visit >>> https://groups.google.com/d/msg/algogeeks/-/BWplK7bCatMJ. >>> >>> To post to this group, send email to algogeeks@googlegroups.com. >>> To unsubscribe from this group, send email to >>> algogeeks+unsubscr...@googlegroups.com. >>> For more options, visit this group at >>> http://groups.google.com/group/algogeeks?hl=en. >>> >> >> >> >> -- >> Cheers, >> >> Nishant Pandey |Specialist Tools Development | >> npan...@google.com<gvib...@google.com> | >> +91-9911258345 >> >> >> > > > -- > Cheers, > > Nishant Pandey |Specialist Tools Development | > npan...@google.com<gvib...@google.com> | > +91-9911258345 > > > -- > 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 > algogeeks+unsubscr...@googlegroups.com. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
