@piyush, Hi, thanks alot for the solution, Thats to find the diameter of a tree. :) But, how would you obtain the 2 nodes which have the max. distance betwn them?
On May 30, 1:17 pm, Vipul Kumar <vipul.k.r...@gmail.com> wrote: > That is same as finding the diameter of the tree. > > > > > > > > On Mon, May 30, 2011 at 1:44 PM, Piyush Sinha <ecstasy.piy...@gmail.com> > wrote: > > There can be two cases to it.... > > > Case 1 - The maximum distance passes through the root node. > > 1 > > / \ > > 2 3 > > / \ > > 4 5 > > Maximum distance is between 4 and 5 i.e. 4 > > > Case 2 - The maximum distance lies in either of the two subtrees > > > 1 > > / \ > > 2 3 > > / \ > > 4 5 > > / \ \ > > 6 7 8 > > / \ > > 9 10 > > / \ > > 11 12 > > > Here the greatest maximum distance is between 11 and 12. i.e 8 > > > Hence, the greatest distance between any two nodes of a tree T is the > > largest of the following quantities: > > > * the greatest distance of T’s left subtree > > * the greatest distance of T’s right subtree > > * the longest path between leaves that goes through the root of T (this can > > be computed from the heights of the subtrees of T) > > > On Mon, May 30, 2011 at 1:26 PM, ross <jagadish1...@gmail.com> wrote: > > >> Given a binary tree(not a BST) find the 2 nodes of the binary tree > >> which are separated by maximum distance. > >> By distance, we mean no. of edges in the path from node1 to node2. > > >> -- > >> 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. > > > -- > > Piyush Sinha > > IIIT, Allahabad > > +91-8792136657 > > +91-7483122727 > >https://www.facebook.com/profile.php?id=100000655377926 > > > -- > > 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.
