TOPICS
Search

Random Recursive Tree


A random recursive tree on vertices 1, 2, ..., n is a random rooted tree with root vertex 1 obtained by attaching each new graph vertex j to a uniformly selected earlier graph vertex. Equivalently, it is uniformly distributed over rooted trees whose labels increase along every path away from the root vertex (Pittel 1994). This distribution differs from the uniform distribution on all labeled trees.

More generally, attachment to a graph vertex with k children may have weight 1+ak. This rule is defined for all positive integers n when a>=0, or when a=-1/d for a positive integer d. For d>=2, the latter rule permits at most d children per graph vertex. The case a=-1 produces a path graph. For a>=0 or a=-1/d with d>=2, the cover time of a random walk on these growing trees has an explicit asymptotic constant depending on a (Angel et al. 2026).


See also

Labeled Tree, Random Graph, Rooted Tree, Tree

Explore with Wolfram|Alpha

References

Angel, O.; Goldschmidt, C.; and Michaeli, P. "Cover Times of Random Recursive Trees and Linear Preferential Attachment Trees." 13 Nov 2026. https://arxiv.org/abs/2611.18353v1.Pittel, B. "Note on the Heights of Random Recursive Trees and Random m-Ary Search Trees." Random Struct. Alg. 5, 337-347, 1994. https://doi.org/10.1002/rsa.3240050207.

Cite this as:

Weisstein, Eric W. "Random Recursive Tree." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/RandomRecursiveTree.html

Subject classifications