20

## 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 `n`

th 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)`

.

So, a binary tree? "a binary tree is a tree data structure in which each node has at most two children" – fəˈnɛtɪk – 2017-03-14T14:19:18.140

3Your description is that of a binary tree. Binary trees do not need to have 2 children. It just means they have at most 2 children. I guess unary-binary is just a more specific term which doesn't really mean anything different. – fəˈnɛtɪk – 2017-03-14T14:22:37.080

Consider clarifying what "BNF" is for those of us who are not computer scientists – Luis Mendo – 2017-03-14T14:46:14.260

1@GuyCoder My point is, if someone sees "BNF" and doesn't know what that means they may be put off and stop reading. Perhaps using the name instead of the acronym and adding a link to the Wikipedia would suffice – Luis Mendo – 2017-03-14T15:35:08.940

I think that since these are binary trees, they should be called binary trees. No sense creating a new term for something that already has a proper name. – mbomb007 – 2017-03-14T16:28:36.853

4@mbomb007 Name changed. I should get a peer-pressure award for that. :) – Guy Coder – 2017-03-14T16:43:47.817

Just make sure that if your friends all jump off a binary bridge that you don't. – mbomb007 – 2017-03-14T16:50:35.967

Not sure about the "this is just a binary tree" talk. In my opinion, if a node in a

usualbinary tree has only one descendant, you could still differentiate between it being the left or right one. – Christian Sievers – 2017-03-14T17:26:39.870