Calculating the smallest possible tree

Question

Given a set of nodes, how can I construct a tree which links together all the nodes in a way which minimises max(max(degree), max(depth))?

For example, given a set of five nodes, I could connect them like so:

However, this is not minimal, since max(degree) == 4 and max(depth) == 1, a better tree would be:

which has max(degree) == 2 and max(depth) == 2

Edit:: The algorithm does not have to be fast, but calculating the absolutely optimal tree is important.

Answer 1

Go from opposite direction. Given a degree and a depth the maximum number of nodes is a sum = 1 + degree + degree^2 + ... + degree^depth. This is integer sequence A031973. You can calculate it each time, or just store first dosen of values. Either case, you search for minimum value that is larger that your node count, and figure out the corresponding D=degree=depth

When you know your D then just fill the tree any way you like, with regard to its bounds.

Answer 2

The maximum number of nodes in a tree with a depth == degree is n = Sum degree^k for k = 0 to degree-1. n fact that sum is a geometric series. Thus its value is equal to (degree^degree-1)/(degree-1) which is probably much faster to calculate. (even though speed didn't matter ;-) ) But you cannot solve the equation n = (degree^degree-1)/(degree-1) algebraically so you will have to store precalculated values of the sum and then choose the value of degree which yields the least possible value still greater/equal to n.