Introduction

I had a project I wanted to work on where it would be nice to have balanced binary trees enumerated. I have since learned of other work on this, but at the time I hadn’t found anything and so worked together with a couple of other coders, usernames Ykulvaarlk and Plakrast on Discord, to figure this out. At the bottom is what I think may be a unique enumeration that enumerates the trees by size. Anyway below is a Wolfram language implementation, plus some interactive explorers.

Mapping Integers to Balanced Binary Trees

Wolfram Language Code


Haskell Code


Exploration

The algorithm for this was described by Ykulvaarlk, and then implemented by Plakrast in Haskell, but here is my Wolfram Language version running. Balanced binary trees correspond uniquely to balanced parenthesis, so I’ve represented them as parentheses here.
In[]:=
Table[enumeratedParentheses[n,"mapping""riffled"],{n,1,20}]//Column
Out[]=
()
()()
(())
()(())
()()()
(())()
()()(())
(())(())
(()())
()(()())
((()))
()((()))
()()(()())
(())(()())
()()((()))
(())((()))
()(())()
()()()()
()(())(())
()()()(())
The “enumeratedTree” function can be used to make nested lists for easier use in other projects:
In[]:=
Table[​​enumeratedTree[n,"mapping""riffled"],​​{n,0,5}]/.​​{}->x//Column
Out[]=
x
{x,x}
{{x,x},x}
{x,{x,x}}
{{x,x},{x,x}}
{{{x,x},x},x}
Here is an interactive explorer
In[]:=
Manipulate[​​enumeratedParentheses[n,"mapping""riffled"],​​{{n,1},0,100,1,Appearance->"Open"},​​SaveDefinitions->True]
Out[]=
​
n
1
()

Mapping Balanced Binary Trees Back to Integers

Code


Exploration

Here we can go back the other way. To demonstrate, I’ve generated enumerated parentheses, then mapped them back to their range of integers:
In[]:=
test=enumeratedParentheses[#,"mapping""riffled"]&/@Range[20]
Out[]=
{(),()(),(()),()(()),()()(),(())(),()()(()),(())(()),(()()),()(()()),((())),()((())),()()(()()),(())(()()),()()((())),(())((())),()(())(),()()()(),()(())(()),()()()(())}
In[]:=
parenthesesIndex[#,"mapping""riffled"]&/@test
Out[]=
{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20}
The same code for use with the List syntax for the Wolfram Language:
In[]:=
treeIndex[{{},{{},{}}},"mapping""riffled"]
Out[]=
3
Put in your own parentheses here to get the corresponding integer:s
In[]:=
Manipulate[​​parenthesesIndex[input,"mapping""riffled"],​​{{input,"()()(())"},InputField[#,String]&},​​SaveDefinitions->True]
Out[]=
​
input
()()(())
7

Mapping integers to binary trees which are ordered by size

Code


Exploration

Finally here they are ordered by size. The code for the mapping is more complex, but it can be nice to have them ordered by size.
In[]:=
Table[enumeratedParentheses[n,"mapping""catalan"],{n,1,20}]//Column
Out[]=
()
(())
()()
((()))
(()())
()(())
(())()
()()()
(((())))
((()()))
(()(()))
((())())
(()()())
()((()))
()(()())
(())(())
()()(())
((()))()
(()())()
()(())()
Another interactive explorer
Manipulate[​​enumeratedParentheses[n,"mapping""catalan"],​​{n,1,30,1,Appearance->"Open"},​​SaveDefinitions->True]
Out[]=
​
n
1
()
I haven’t gotten this to work in the reverse direction, yet, however, though it should be doable in principle.

CITE THIS NOTEBOOK

Enumerating balanced binary trees​
by Eric Parfitt​
Wolfram Community, STAFF PICKS, March 28, 2025
​https://community.wolfram.com/groups/-/m/t/3434372