Here's the crude algo : First find the node having the max depth in the left sub tree and then find the node having the max depth in the right sub tree. Ties are broken arbitrarily. These will be the 2 nodes separated by the maximum distance. The sum of their depths will give us the distance
Ankit On Mon, May 30, 2011 at 1:17 AM, Aakash Johari <[email protected]>wrote: > yes, it is the diameter of the tree. > > > On Mon, May 30, 2011 at 1:17 AM, Vipul Kumar <[email protected]>wrote: > >> That is same as finding the diameter of the tree. >> >> On Mon, May 30, 2011 at 1:44 PM, Piyush Sinha <[email protected]> >> 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 <[email protected]> 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 [email protected]. >> >> To unsubscribe from this group, send email to >> >> [email protected]. >> >> 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 [email protected]. >> > To unsubscribe from this group, send email to >> > [email protected]. >> > 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 [email protected]. >> To unsubscribe from this group, send email to >> [email protected]. >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> >> > > > -- > -Aakash Johari > (IIIT Allahabad) > > > > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]. > 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 [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
