Finding the minimum number of calls in a tree

Question

I was asked this question in an interview and struggled to answer it correctly in the time allotted. Nonetheless, I thought it was an interesting problem, and I hadn't seen it before.

Suppose you have a tree where the root can call (on the phone) each of it's children, when a child receives the call, he can call each of his children, etc. The problem is that each call must be done in a number of rounds, and we need to minimize the number of rounds it takes to make the calls. For example, suppose you have the following tree:

   A
  / \
 /   \
 B    D
 |
 |
 C

One solution is for A to call D in round one, A to call B in round two, and B to call C in round three. The optimal solution is for A to call B in round one, and A to call D and B to call C in round two.

Note that A cannot call both B and D in the same round, nor can any node call more than one of its children in the same round. However, multiple nodes with a different parent can call simultaneously. For example, given the tree:

      A
    / | \
   /  |  \
   B  C   D
  /\      |
 /  \     |
E   F     G

We can have a sequence (where "-" separates rounds), such as:

A B - B E, A D - B F, A C, D G

(A calls B first round, B calls E and A calls D second, ...)

I'm assuming some type of dynamic programming can be used, but I'm not sure which direction to take this in. My initial inclination is to use DFS to order the longest path from the root to leaves in decreasing order, but when it comes to the nodes actually making calls, I'm not sure how we can achieve optimality given any tree, nor how we can output the paths that the optimal calls would make (i.e. in the first example we could output

A B - B C, A D

Answer 1

You can traverse the tree in postorder and compute for each node the number of rounds that the subtree below that node needs as follows:

• If the node is a leaf, the subtree takes 0 rounds.
• If the node is not a leaf, sort its children by the number of rounds their respective subtrees take, from longest to shortest. You will traverse them in this order. The number of rounds for the current node is $\max_i\{n_i +i\}$, where $n_i$ is the number of rounds the subtree of the $i$-th child (in sorted order) takes.

Regarding output: The best format depends on what you want to do with the data. Do you need information on which calls happen concurrently? Or do you want to actually implement the calls?
In the latter case, listing the processing order for each node seems like a reasonable format.
In the former case, your format is nice, but probably needs an additional traversal to be obtained.