On Jul 3, 10:14 am, jalaj jaiswal <[email protected]> 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 [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.
