10
\$\begingroup\$

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.

\$\endgroup\$
4
  • \$\begingroup\$ I was thinking about that problem when I was trying to make a maze-like writing system \$\endgroup\$
    – Ming-Tang
    Aug 13, 2011 at 5:51
  • \$\begingroup\$ What is the standard deadline before declaring a solution? \$\endgroup\$
    – Kyle Butt
    Aug 15, 2011 at 1:00
  • \$\begingroup\$ Would there be any interest in doing a slight variation of this problem, where the output was required to be ordered, and streaming? \$\endgroup\$
    – Kyle Butt
    Aug 15, 2011 at 20:54
  • 1
    \$\begingroup\$ @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. \$\endgroup\$
    – migimaru
    Aug 16, 2011 at 12:32

8 Answers 8

3
\$\begingroup\$

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;
}
\$\endgroup\$
2
\$\begingroup\$

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";}
\$\endgroup\$
2
\$\begingroup\$

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.

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

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
\$\endgroup\$
0
\$\begingroup\$

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
\$\endgroup\$
1
  • \$\begingroup\$ Note that I don't intend to accept this as the answer, just thought I would toss mine out there. \$\endgroup\$
    – Kyle Butt
    Aug 15, 2011 at 21:02
0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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!

\$\endgroup\$
0
\$\begingroup\$

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

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.