Enumerate all binary trees with n nodes

Question

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.

• Ming-Tang: I was thinking about that problem when I was trying to make a maze-like writing system
• Kyle Butt: What is the standard deadline before declaring a solution?
• Kyle Butt: Would there be any interest in doing a slight variation of this problem, where the output was required to be ordered, and streaming?
• migimaru: @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.

Answer 1

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;
}

Answer 2

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])-1;$i<=2*$p;){$s=$d=decbin($i++);while($o!=$s=str_replace(100,0,$o=$s));echo$s?:"$d\n";}

Answer 3

Ruby, (削除) 99 (削除ここまで) (削除) 94 (削除ここまで) (削除) 92 (削除ここまで) (削除) 89 (削除ここまで) 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.

• Lowjacker: It would be one character shorter to accept input from stdin.
• Lowjacker: Also, you don't need the *?\n, because puts prints each element of the array in its own line.
• migimaru: 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.
• migimaru: Also, sub! is sufficient here instead of gsub!, so that's another character you could save.
• Howard: @migimaru You are right with both of your comments. Thanks a lot.

Answer 4

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

Answer 5

Haskell 122 chars

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

• Kyle Butt: Note that I don't intend to accept this as the answer, just thought I would toss mine out there.

Answer 6

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.

Answer 7

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!

Answer 8

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)))
 }
}