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 + 1;
else result = 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 <rajkuma...@gmail.com <javascript:>> 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 algogeeks+...@googlegroups.com <javascript:>.
> >
>
--
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 algogeeks+unsubscr...@googlegroups.com.
