hi, given a tree with N nodes find the node such that its average total distance from each other node is smallest
i.e. if nodes are labeled 0....N-1 then find i such that [ SUM d(i, j ){0<=j<N}] /N is minimum NOTE: This is different from the classic problem of finding tree center where tree center is the node such that its maximum distance to other nodes is minmum this must be done is O(n) time and O(n) space sample input : an integer array Tree with N elements where each element T[a]=b represents an edge (a,b) when a!=b Tree[]={14,9,11,16,14,0,11,6,14,11,3 ,16,13,17,12, 1, 5,17} correct answer is 16. My solution was to find (SUM(i,j) {0<=j<N})/N for any one value of i using dfs then find it for other is value of i's by the fact that if there is an edge in tree (a,b) and average total distance for node a is X and then average total distance for node be can be found in constant time as follows if we remove the edge (a,b) from the tree then there will be two connected components in the tree one that contains node a and other that contains node b. Let number of nodes in first be Na and number of nodes in second be Nb then average total distance of node b is = X + Na - Nb. Na, and Nb can be found in linear time again using dfs for each node. Somehow this solution gives wrong answer , Any Help ????? -- 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.