Given the collection of nodes that constitute the diameter of the tree, The node with Max height among them i.e the node thats closest to the root(top level node) need not necessarily have children with equal height.
For Instance: If the the top_level_node->left->height < top_level_node->right->height , then find p such that p = top_level_node->right->height - top_level_node->left->height - 1; now traverse down p levels to the right along the path that constitutes the diameter. this node will be the center of the tree. @gene : you mentioned within brackets "(though not necessarily the overall maximum)".Did you mean the same as i do ? On Sun, Jul 4, 2010 at 2:19 AM, Gene <gene.ress...@gmail.com> wrote: > On Jul 3, 10:14 am, jalaj jaiswal <jalaj.jaiswa...@gmail.com> wrote: > > give an algo to find center of a tree > > conter of a tree is midpoint of diameter which is the largest distance > b/w > > any two nodes > > You can traverse the tree once in O(n) to label each node N with its > height H(N), which is the maximum distance to any descendent leaf. > > Then traverse it again looking for a node C with H(C->left) = H(C- > >right) and the maximum value of D(C) = 1 + H(C->left) + H(C->right). > The first condition puts C in the middle of some maximal length path > (though not necessarily the overall maximum). The second picks the > center IF there is only one center. > > A tree can also have 2 centers. For example in the tree > > 1 --> 2 --> 3 > \ --> 4 > > both 1 and 2 are centers because their radius is 1 in both cases. > Working out how to handle this case is not hard. > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algoge...@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@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 algoge...@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.
