Encyclopedia

Random recursive tree

Wikipedia contributorsAdapted for Fathomly · View authors

1 min read
Source updated December 27, 2025

In probability theory, a random recursive tree is a rooted tree chosen uniformly at random from the recursive trees with a given number of vertices.

01Definition and generation

In a recursive tree with $n$ vertices, the vertices are labeled by the numbers from $1$ to $n$ , and the labels must decrease along any path to the root of the tree. These trees are unordered, in the sense that there is no distinguished ordering of the children of each vertex. In a random recursive tree, all such trees are equally likely.

Alternatively, a random recursive tree can be generated by starting from a single vertex, the root of the tree, labeled $1$ , and then for each successive label from $2$ to $n$ choosing a random vertex with a smaller label to be its parent. If each of the choices is uniform and independent of the other choices, the resulting tree will be a random recursive tree.

02Properties

With high probability, the longest path from the root to the leaf of an $n$ -vertex random recursive tree has length $e\log n$ . The maximum number of children of any vertex, i.e., degree, in the tree is, with high probability, $(1\pm o(1))\log _{2}n$ . The expected distance of the $k$ th vertex from the root is the $k$ th harmonic number, from which it follows by linearity of expectation that the sum of all root-to-vertex path lengths is, with high probability, $(1\pm o(1))n\log n$ . The expected number of leaves of the tree is $n/2$ with variance $n/12$ , so with high probability the number of leaves is $(1\pm o(1))n/2$ .

03Applications

Zhang (2015) lists several applications of random recursive trees in modeling phenomena including disease spreading, pyramid schemes, the evolution of languages, and the growth of computer networks.

Watch videos about Random recursive treeExplainers and documentaries on YouTube (opens in a new tab)

Sources and credits

This article is adapted from the Wikipedia article “Random recursive tree”, written by its contributors and licensed under CC BY-SA 4.0. Fathomly has changed the layout, removed citation markers, navigation and maintenance notices, and adjusted punctuation. This adapted version is shared under the same license. For references, see the original article.

Fathomly is not affiliated with or endorsed by the Wikimedia Foundation. Spotted a problem? Tell us.