# Enumerate all binary trees with n nodes

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 Aug 13, 2011 at 5:51
• What is the standard deadline before declaring a solution? Aug 15, 2011 at 1:00
• Would there be any interest in doing a slight variation of this problem, where the output was required to be ordered, and streaming? Aug 15, 2011 at 20:54
• @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. Aug 16, 2011 at 12:32

## Perl - 125 79 chars

Count includes 4 chars for "-ln" options. Takes n from stdin.

New constructive approach:

@a=0;map{%a=();map{$a{"$100$'"}=1while/0/g;}@a;@a=keys%a}1..$_;print for@a


Form the solution for n by substituting a new internal node ("100") for each leaf ("0"), in turn, in each tree from the solution for n-1.

(I owe this concept to other's solutions that use the internal node to leaf [100->0] substitution for verifying sequentially-generated strings, and I believe I saw--after writing my answer based on that concept--this same 0->100 method of construction in someone's intermediate edit.)

Previous recursive approach:

sub t{my$n=shift;if($n){--$n;for$R(0..$n){for$r(t($R)){for$l(t($n-$R)){push@_,"1$l$r"}}}}else{push@_,"0"}@_}print for t$_  Recursive ungolfed: sub tree { my ($n) = @_;
my @result = ();
if ( $n ) { for$right_count ( 0 .. $n-1 ) { for$right ( tree( $right_count ) ) { for$left ( tree( ($n-1) -$right_count ) ) {
push @result, "1$left$right";
}
}
}
}
else {
push @result, "0";
}
return @result;
}
foreach $tree ( tree($_) ) {
print $tree; }  ## PHP (142)(138)(134) (113) Runs from the command line, i.e. "php golf.php 1" outputs "100". EDIT: Cut 4 characters with an alternate method, building up the strings from 0 rather than recursing down from$n. Uses PHP 5.3 for the shortened ternary operator; otherwise, 2 more characters are needed.

EDIT 2: Saved 4 more characters with some changes to the loops.

EDIT 3: I was trying a different approach and I finally got it below the old method.

All of the trees can be considered as binary representations of integers between 4^n (or 0, when n=0) and 2*4^n. This function loops through that range, and gets the binary string of each number, then repeatedly reduces it by replacing "100" with "0". If the final string is "0", then it's a valid tree, so output it.

for($i=$p=pow(4,$argv)-1;$i<=2*$p;){$s=$d=decbin($i++);while($o!=$s=str_replace(100,0,$o=$s));echo$s?:"$d\n";}


### Ruby, 99949289 87 characters

(n=4**gets.to_i).times{|i|s=(n+i-1).to_s 2;t=s*1;0while s.sub!'100',?0;puts t if s==?0}


The input is read from stdin.

> echo 2 | ruby binary_trees.rb
10100
11000


Edit 1: Changed IO (see Lowjacker's comments)

b=->n{n==0?[?0]:(k=[];n.times{|z|b[z].product(b[n-1-z]){|l|k<<=?1+l*''}};k)}
puts b[gets.to_i]


Edit 2: Changed algorithm.

b=->n{n==0?[?0]:(k=[];b[n-1].map{|s|s.gsub(/0/){k<<=$+'100'+$'}};k.uniq)}
puts b[gets.to_i]


Edit 3: The version now takes the third approach (using the idea of migimaru).

Edit 4: Again two characters. Thank you to migimaru.

• It would be one character shorter to accept input from stdin. Aug 13, 2011 at 12:09
• Also, you don't need the *?\n, because puts prints each element of the array in its own line. Aug 13, 2011 at 12:18
• I just started trying to learn Ruby, but I think you can save a character by using 0while instead of {}while. At least it works in NetBeans. Aug 13, 2011 at 16:15
• Also, sub! is sufficient here instead of gsub!, so that's another character you could save. Aug 13, 2011 at 16:33
• @migimaru You are right with both of your comments. Thanks a lot. Aug 13, 2011 at 17:00

## Ruby 1.9 (80) (79)

Using the non-recursive, constructive approach used by DCharness.

EDIT: Saved 1 character.

s=*?0;gets.to_i.times{s.map!{|x|x.gsub(?0).map{$+'100'+$'}}.flatten!}
puts s&s


main=do n<-readLn;mapM putStrLn$g n n g 0 0=[['0']] g u r|r<u||u<0=[] g u r=do s<-[1,0];map((toEnum$s+48):)$g(u-s)(r-1+s)  Since the IO is a non-trivial portion of the code in haskell, maybe someone can use a similar solution in another language. Essentially random walks in a square from bottom left to top right stopping if the diagonal is crossed. Equivalent to the following: module BinTreeEnum where import Data.List import Data.Monoid data TStruct = NonEmpty | Empty deriving (Enum, Show) type TreeDef = [TStruct] printTStruct :: TStruct -> Char printTStruct NonEmpty = '1' printTStruct Empty = '0' printTreeDef :: TreeDef -> String printTreeDef = map printTStruct enumBinTrees :: Int -> [TreeDef] enumBinTrees n = enumBinTrees' n n where enumBinTrees' ups rights | rights < ups = mempty enumBinTrees' 0 rights = return (replicate (rights+1) Empty) enumBinTrees' ups rights = do step <- enumFrom (toEnum 0) let suffixes = case step of NonEmpty -> enumBinTrees' (ups - 1) rights Empty -> enumBinTrees' ups (rights - 1) suffix <- suffixes return (step:suffix) mainExample = do print$ map printTreeDef $enumBinTrees 4  • Note that I don't intend to accept this as the answer, just thought I would toss mine out there. Aug 15, 2011 at 21:02 ## Golfscript, 60 83 ~[1,]\,{;{[:l.,,]zip{({;}{~:a;[l a<~1 0.l a)>~]}if}/}%}/{n}%  I built a golfscript mode for Emacs for working on this, if anyone's interested. # Haskell, 54 bytes t 0=["0"] t n=['1':l++r|m<-[0..n-1],l<-t m,r<-t$n-1-m]


Try it online!

# Scala, 115 bytes

It reminds me of Catalan number.

Golfed version. Try it online!

n=>n match{case 0=>Seq("0");case _=>(for(m<-0 until n)yield{for{l<-t(m);r<-t(n-1-m)}yield "1"+l+r}).toList.flatten}


Ungolfed version. Try it online!

object Main {
def t(n: Int): List[String] = n match {
case 0 => List("0")
case _ =>
(for (m <- 0 until n) yield {
for {
l <- t(m)
r <- t(n - 1 - m)
} yield "1" + l + r
}).toList.flatten
}

def main(args: Array[String]): Unit = {
(0 to 3).foreach(n => println(t(n)))
}
}

`