A random tree on n nodes has a height (longest path from root to leaf) and a width (largest number of nodes at any single depth). For specific tree distributions — uniform random labeled trees, Galton-Watson trees with known offspring distributions — both quantities are well studied. The height is typically O(√n) and the width is typically O(√n), so their product is typically O(n).
The question: does this hold universally? For trees with arbitrary degree sequences, conditioned Bienaymé trees, simply generated trees — any reasonable definition of “random tree” — is the product of height and width always O(n)?
The answer is O(n log n), and this is tight. The extra logarithmic factor is not an artifact of the proof but a genuine feature: there exist degree sequences where the product reaches Θ(n log n). The bound requires no assumptions on the degree distribution — it holds uniformly across all random tree families.
The proof establishes non-asymptotic, assumption-free concentration bounds. The key is that height and width are not independent — a tree cannot be simultaneously very tall and very wide, because the total number of nodes constrains their product. But the constraint is looser than the naive O(n) by a logarithmic factor, and achieving tightness requires degree sequences that force the tree into an unusual shape: tall enough and wide enough to saturate the bound.
The structural point: the geometric constraint between height and width is nearly but not exactly what intuition suggests. The product is controlled by n, not √n × √n, because the typical behavior (both O(√n)) is not the worst case. The logarithmic gap between typical and universal is the cost of making no assumptions.