10
1
Given an integer n, enumerate all possible full binary trees with n internal nodes. (Full binary trees have exactly 2 children on every internal node). The tree structure should be output as a pre-order traversal of the tree with 1 representing an internal node, and 0 representing an external node (Null).
Here are examples for the first few n:
0:
0
1:
100
2:
11000
10100
3:
1110000
1101000
1100100
1011000
1010100
This is a code golf with the prize going to fewest characters. The trees should be output one per line to stdout. The program should read n from the commandline or stdin.
I was thinking about that problem when I was trying to make a maze-like writing system – Ming-Tang – 2011-08-13T05:51:44.807
What is the standard deadline before declaring a solution? – Kyle Butt – 2011-08-15T01:00:19.443
Would there be any interest in doing a slight variation of this problem, where the output was required to be ordered, and streaming? – Kyle Butt – 2011-08-15T20:54:09.487
@Kyle Butt Just my opinion, but I don't think I'd be interested. For me, part of the fun with these problems is trying alternative approaches, and requiring a certain order would likely limit the number of viable algorithms. – migimaru – 2011-08-16T12:32:03.333