Width Three Is Best

N = 1 + W + … + W^D = (W^D+1 − 1) / (W − 1).

Or, for a fixed number of nodes, the depth can be computed from the width, and vice versa.

D = { ln [ 1 + N(W−1) ] / ln W } − 1

When fully expanded, the table of contents for such a tree will occupy one line for the root node plus W content lines and one blank line per layer of depth.

L = 1 + D(W+1)

Given a fixed number of nodes, we can substitute for D to obtain the number of lines L as a function of W, then minimize over W to determine the optimum width. I couldn't find a nice analytical solution, but here are some numerical results, courtesy of Mathematica.

N	W
103	3.32
106	3.46
109	3.50
1012	3.53

These are surprising results—for all practical purposes, width three is best, with width four being next best. By the way, Mathematica couldn't find a nice analytical solution either, but it had a different way of saying so.

The equations appear to involve transcendental functions of the variables in an essentially non-algebraic way.

A better way to look at the problem is to consider the number of lines L as fixed, and see how the number of nodes varies as a function of W. The case L = 37 is both realistic and numerically convenient.

W	W+1	D	N
2	3	12	8191
3	4	9	29524
4	5	7.2	28824.76
5	6	6	19531
6	7	5.14	12052.99
7	8	4.5	7411.02

The above arguments show that width three is best, if the only criterion is the number of lines in the table of contents … but of course there are other criteria. One might like to reduce the number of mouse clicks needed to reach the bottom of the tree, i.e., minimize the depth; equivalently, one might like to increase the amount of contextual information presented to the user, i.e., maximize the width.

As often happens, the different criteria are in opposition; some intermediate balance must be found. Since widths three and four are both pretty good as far as number of lines is concerned, width four, or even five, might actually be best.