# Finding the minimum number of calls in a tree

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

• 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.