Wolfram Function Repository

Instant-use add-on functions for the Wolfram Language

Function Repository Resource:

 RandomBinaryTree

Source Notebook

Generate a random binary tree

Contributed by: Ian Ford (Wolfram Research)

ResourceFunction["RandomBinaryTree"][n]

gives a pseudorandom binary tree with n leaf nodes.

ResourceFunction["RandomBinaryTree"][n,k]

gives a list of k pseudorandom binary trees.

ResourceFunction["RandomBinaryTree"][n,{k1,k2,…}]

gives a k1×k2×… array of binary trees.

Details and Options

ResourceFunction["RandomBinaryTree"][n] samples from the discrete uniform distribution over the n!Cn-1 leaf-labeled, rooted, ordered binary trees with n leaf nodes, where Cn-1 is given by CatalanNumber[n-1]. Any reordering of the data or subtrees represents a different binary tree.
ResourceFunction["RandomBinaryTree"] gives a different sequence of pseudorandom trees whenever you run the Wolfram Language. By using SeedRandom, you can get a repeatable sequence.
The data of the leaves produced by ResourceFunction["RandomBinaryTree"][n,…] is taken to be integers 1, …, n.
ResourceFunction["RandomBinaryTree"] takes the same options as Tree.

Examples

Basic Examples (3) 

Generate a random binary tree with 10 leaf nodes:

In[1]:=
ResourceFunction["RandomBinaryTree"][10]
Out[1]=

Generate a list of random binary trees:

In[2]:=
ResourceFunction["RandomBinaryTree"][5, 3]
Out[2]=

Generate an array of random binary trees:

In[3]:=
ResourceFunction["RandomBinaryTree"][5, {2, 3}]
Out[3]=

Properties and Relations (5) 

RandomBinaryTree uses integer data:

In[4]:=
ResourceFunction["RandomBinaryTree"][7]
Out[4]=

Use TreeMap to replace data in the binary tree:

In[5]:=
TreeMap[f, %, "Leaves"]
Out[5]=

RandomBinaryTree gives pseudorandom binary trees:

In[6]:=
{ResourceFunction["RandomBinaryTree"][6], ResourceFunction["RandomBinaryTree"][6]}
Out[6]=

Use SeedRandom to get repeatable random binary trees:

In[7]:=
{SeedRandom[1]; ResourceFunction["RandomBinaryTree"][6], SeedRandom[1]; ResourceFunction["RandomBinaryTree"][6]}
Out[7]=

Use BlockRandom to block one use of RandomBinaryTree from affecting others:

In[8]:=
{BlockRandom[ResourceFunction["RandomBinaryTree"][6]], ResourceFunction["RandomBinaryTree"][6], ResourceFunction["RandomBinaryTree"][6]}
Out[8]=

RandomBinaryTree[n] can produce n!CatalanNumber[n-1] different binary trees:

In[9]:=
Table[n! CatalanNumber[n - 1], {n, 1, 8}]
Out[9]=
In[10]:=
ResourceFunction["RandomBinaryTree"][2, 20] // DeleteDuplicates
Out[10]=
In[11]:=
ResourceFunction["RandomBinaryTree"][3, 200] // DeleteDuplicates // Length
Out[11]=
In[12]:=
ResourceFunction["RandomBinaryTree"][4, 2000] // DeleteDuplicates // Length
Out[12]=
In[13]:=
ResourceFunction["RandomBinaryTree"][5, 100000] // DeleteDuplicates // Length
Out[13]=

RandomBinaryTree[n] samples from the uniform distribution over the leaf-labeled, rooted, ordered binary trees with n leaf nodes:

In[14]:=
ResourceFunction["RandomBinaryTree"][3, 10000, ImageSize -> 50] // Sort // Tally
Out[14]=

Version History

  • 1.0.0 – 03 February 2023

Source Metadata

Related Resources

License Information