Binary trees
A binary tree is a tree with nodes of three types:
- terminal nodes, which have no children
- unary nodes, which have one child each
- binary nodes, which have two children each
We can represent them with the following grammar, given in BNF (Backus–Naur form):
<e> ::=
<terminal>
| <unary>
| <binary>
<terminal> ::=
"0"
<unary> ::=
"(1" <e> ")"
<binary> ::=
"(2" <e> " " <e> ")"
In this grammar the nodes are given in preorder and each node is represented by a digit which is the number of children it has.
Motzkin numbers
Motzkin numbers (OEIS) (Wikipedia) have many interpretations, but one interpretation is that the nth Motzkin number is the number of distinct binary trees with n nodes. A table of Motzkin numbers starts
N Motzkin number M(N)
1 1
2 1
3 2
4 4
5 9
6 21
7 51
8 127
...
e.g. M(5) is 9, and the nine distinct binary trees with 5 nodes are
1 (1 (1 (1 (1 0))))
2 (1 (1 (2 0 0)))
3 (1 (2 0 (1 0)))
4 (1 (2 (1 0) 0))
5 (2 0 (1 (1 0)))
6 (2 0 (2 0 0))
7 (2 (1 0) (1 0))
8 (2 (1 (1 0)) 0)
9 (2 (2 0 0) 0)
Task
Take a single positive integer n as input and output all of the distinct binary trees with n nodes.
Examples for n from 1 to 5 with parenthesis included for readability
0
(1 0)
(1 (1 0))
(2 0 0)
(1 (1 (1 0)))
(1 (2 0 0))
(2 0 (1 0))
(2 (1 0) 0)
(1 (1 (1 (1 0))))
(1 (1 (2 0 0)))
(1 (2 0 (1 0)))
(1 (2 (1 0) 0))
(2 0 (1 (1 0)))
(2 0 (2 0 0))
(2 (1 0) (1 0))
(2 (1 (1 0)) 0)
(2 (2 0 0) 0)
Input
The input will be one positive integer.
Output
The output should be an intelligible representation of the distinct binary trees with that many nodes. It is not compulsory to use the exact string given by the BNF grammar above: it is sufficient that the syntax used give an unambiguous representation of the trees. E.g. you could use [] instead of (), an extra level of brackets [[]] instead of [], outer parenthesis are present or missing, extra commas or no commas, extra spaces, parenthesis or no parenthesis, etc.
All of these are equivalent:
(1 (2 (1 0) 0))
[1 [2 [1 0] 0]]
1 2 1 0 0
12100
(1 [2 (1 0) 0])
.:.--
*%*55
(- (+ (- 1) 1))
-+-11
Also a variation purposed by @xnor in a comment. Since there is a way to translate this to a format that can be understood it is acceptable.
[[[]][]] is (2 (1 0) 0)
To make this easier to understand convert some of the [] to () like so
[([])()]
Now if you start with
[]
then insert a binary which needs two expressions you get
[()()] which is 2
and then for the first () insert a unary which needs one expression you get
[([])()] which is 21
but since [] or () with no inner bracketing can represent 0 which needs no more expressions you can interpret it as
2100
Note that answers should work theoretically with infinite memory, but will obviously run out of memory for an implementation-dependent finite input.
Variations of output
BNF xnor Christian Ben
b(t, b(t, t)) [{}{{}{}}] (0(00)) (1, -1, 1, -1)
b(t, u(u(t))) [{}{(())}] (0((0))) (1, -1, 0, 0)
b(u(t), u(t)) [{()}{()}] ((0)(0)) (1, 0, -1, 0)
b(b(t, t), t) [{{}{}}{}] ((00)0) (1, 1, -1, -1)
b(u(u(t)), t) [{(())}{}] (((0))0) (1, 0, 0, -1)
u(b(t, u(t))) [({}{()})] ((0(0))) (0, 1, -1, 0)
u(b(u(t), t)) [({()}{})] (((0)0)) (0, 1, 0, -1)
u(u(b(t, t))) [(({}{}))] (((00))) (0, 0, 1, -1)
u(u(u(u(t)))) [(((())))] ((((0)))) (0, 0, 0, 0)
A possible place to check for duplicate trees
One place to check for a duplicate is with M(5).
This one tree was generated twice for M(5) from M(4) trees
(2 (1 0) (1 0))
the first by adding a unary branch to
(2 (1 0) 0)
and second by adding a unary branch to
(2 0 (1 0))
Understanding BNF
BNF is composed of simple rules:
<symbol> ::= expression
where on the left is a symbol name surrounded by <>.
On the right is the expression for constructing the symbol.
Some rules use other rules in the construction, e.g.
<e> ::= <terminal>
e can be a terminal
and some rules have characters that are used in constructing the symbol, e.g.
<terminal> ::= "0"
terminal is just the character zero.
Some rules have multiple ways of constructing them, e.g.
<e> ::=
<terminal>
| <unary>
| <binary>
An e can be a <terminal> or a <unary> or a <binary>.
And some rules are a sequence of parts, e.g.
<unary> ::= "(1" <e> ")"
A unary is the characters (1 followed by what can be constructed for e followed by ).
You always start with the starting rule, which for this <e>.
Some simple examples:
The simplest sequence is just 0. So we start with the starting rule <e> and see that there are three choices:
<terminal>
| <unary>
| <binary>
so take the first one <terminal>. Now a terminal has no choices and is 0. So replace <terminal> with 0 in the <e> rule and you are done.
Then next one is (1 0). Start with <e> and use rule <unary> which has
"(1" <e> ")"
Now this needs an <e> so we go back to <e> and make a choice of one of the three, this time choosing, <terminal> which gives 0. Replacing 0 into (1 <e> ) gives (1 0), and this is replaced into <unary> so <e> is (1 0).
