I forgot to mention that the tree is n-ary tree, it need not be a binary tree. So what is the approach ?
On 7 November 2013 01:04, Don <[email protected]> wrote: > Atul, the depth is the important factor, not the number of nodes. > If you always pass the message to the deeper subtree first, followed by > the other subtree, you get the minimum number of rounds. > > The problem is to compute the required number of rounds. This can be done > in a way similar to computing the depth of a tree. However, be careful to > handle the case where the subtrees take an equal number of rounds. > > int numRounds(TreePtr t) > { > int result = 0; > if (t) > { > int L = numRounds(t->left); > int R = numRounds(t->right); > if (L == R) result = R + 2; > else result = 1 + max(L,R); > > } > return result; > } > > On Friday, November 1, 2013 1:49:33 AM UTC-4, atul007 wrote: > >> we can first count number of nodes in a subtree below each node.Now >> transfer message to max(count(root->left),count->root->right); >> >> On 11/1/13, kumar raja <[email protected]> wrote: >> > Suppose we need to distribute a message to all the nodes in a rooted >> tree. >> > Initially, only the root >> > node knows the message. In a single round, any node that knows the >> message >> > can forward it >> > to at most one of its children. Design an algorithm to compute the >> minimum >> > number of rounds >> > required for the message to be delivered to all nodes. >> > >> > -- >> > You received this message because you are subscribed to the Google >> Groups >> > "Algorithm Geeks" group. >> > To unsubscribe from this group and stop receiving emails from it, send >> an >> > email to [email protected]. >> > >> > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to [email protected]. > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected].
