Introduction

RandomTree.jl is a Julia package for simulations on random trees, in particular Conditional Galton-Watson trees. It can efficiently generate several types of random trees up to size 10^8, including

• Conditional Galton Watson tree
  • Cayley
  • Binary
  • Catalan
  • DAry
  • Motzkin
• Random Recursive Trees (up to size 10^7)

as well as carry out these simulations

• k-cut
• sum of log(subtree sizes) over all fringe subtrees
• height
• total path length
• leaf number count

The package also provides a simply function for drawing trees.

You can use RandomTree.jl as a library in your code, in Julia REPL, or in a Jupyter notebook. It can also run as a standalone script.

The generation of conditional Galton-Watson trees uses a very efficient algorithm introduced by Luc Devroye. Generating a Galton-Watson tree of 1 million nodes takes about 20-30 ms.