Binary tree fractal

Question

Today's challenge is to draw a binary tree as beautiful ascii-art like this example:

                               /\
                              /  \
                             /    \
                            /      \
                           /        \
                          /          \
                         /            \
                        /              \
                       /                \
                      /                  \
                     /                    \
                    /                      \
                   /                        \
                  /                          \
                 /                            \
                /                              \
               /\                              /\
              /  \                            /  \
             /    \                          /    \
            /      \                        /      \
           /        \                      /        \
          /          \                    /          \
         /            \                  /            \
        /              \                /              \
       /\              /\              /\              /\
      /  \            /  \            /  \            /  \
     /    \          /    \          /    \          /    \
    /      \        /      \        /      \        /      \
   /\      /\      /\      /\      /\      /\      /\      /\
  /  \    /  \    /  \    /  \    /  \    /  \    /  \    /  \
 /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\
/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\

You will be given a positive integer as input. This input is the height of the tree. The above example has a height of six.

You may submit either a full-program or a function, and you are free to use any of our default IO methods. For example, printing the tree, returning a string with newlines, returning a 2d char array, saving the tree to a file, etc. would all be allowed.

Trailing spaces on each line are permitted.

Here are some examples of inputs and their corresponding outputs:

1:
/\

2:
 /\
/\/\

3:
   /\
  /  \
 /\  /\
/\/\/\/\

4:
       /\
      /  \
     /    \
    /      \
   /\      /\
  /  \    /  \
 /\  /\  /\  /\
/\/\/\/\/\/\/\/\

5:
               /\
              /  \
             /    \
            /      \
           /        \
          /          \
         /            \
        /              \
       /\              /\
      /  \            /  \
     /    \          /    \
    /      \        /      \
   /\      /\      /\      /\
  /  \    /  \    /  \    /  \
 /\  /\  /\  /\  /\  /\  /\  /\
/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\

Unfortunately, the output grows exponentially, so it's hard to show larger examples. Here is a link to the output for 8.

As usual, this is a code-golf challenge, so standard loopholes apply, and try to write the shortest program possible in whatever language you choose.

Happy golfing!

Answer 1

Python 2, 77 bytes

S=s=i=2**input()
while s:print S/s*('/'+' '*(s-i)+'\\').center(s);i-=2;s/=s/i

Prints with trailing spaces, terminating with error.

I took this code from my submission to a challenge I posed on Anarchy Golf, plus a one-byte improvement found by xsot. The hardcoded value of 128 was changed to 2**input().

The idea is that each row of the output is a segment copied one or more times. The half after the input split has one copy of each segment, the quarter after the next split has two copies, and so on, until the last line with many segments of /\.

Each segment had a / and \, with spaces in between, as well as on the outside to pad to the right length. The outer padding is done with center.

The variable s tracks the current with of each segment, and the number of segments is S/s so that the total width is the tree width S. The line number i counts down by 2's, and whenever the value s is half of it, a split occurs, and the segment width halves. This is done via the expression s/=s/i. When i reaches 0, this gives an error that terminates the program.

Since anagolf only allows program submissions, I didn't explore the possibility of a recursive function, which I think is likely shorter.

Answer 2

V, 32 bytes

é\é/À­ñLyPÄlx$X>>îò^llÄlxxbPò
|

Try it online!

Hexdump:

00000000: e95c e92f c0ad f116 4c79 50c4 6c78 2458  .\./....LyP.lx$X
00000010: 3e3e eef2 5e6c 6cc4 6c78 7862 50f2 0a7c  >>..^ll.lxxbP..|

Answer 3

Canvas, 11 bytes

/║╶╷［ｌ＼；∔↔║

Try it here!

Explanation:

/║          push `/\` ("/" palindromized so this is a Canvas object)
  ╶╷[       repeat input-1 times
     l        get the width of the ToS
      \       create a diagonal that long
       ;∔     prepend that to the item below
         ↔    reverse the thing horizontally
          ║   and palindromize it horizontally

Answer 4

Haskell, 140 138 135 bytes

e n=[1..n]>>" "
n!f=(e n++).(++e n)<$>f
f 0=[]
f n=1!f(n-1)++['/':e(2*n-2)++"\\"]
b n|n<2=f 1|t<-b$n-1,m<-2^(n-2)=m!f m++zipWith(++)t t

Try it online! Call with b 5, returns a list of strings.

Pretty print usage:

*Main> putStr . unlines $ b 5
               /\
              /  \
             /    \
            /      \
           /        \
          /          \
         /            \
        /              \
       /\              /\
      /  \            /  \
     /    \          /    \
    /      \        /      \
   /\      /\      /\      /\
  /  \    /  \    /  \    /  \
 /\  /\  /\  /\  /\  /\  /\  /\
/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\

(some) Explanation:

• e n generates a string of n spaces
• n!f pads each string in the list of strings f with n spaces left and right
• f n draws a "peak" in a n by 2n rectangle
• b n draws the binary tree by concatenating two smaller trees and centers a new peak above them

Edit: -3 bytes thanks to Zgarb!

Answer 5

J, 49 43 42 bytes

' /\'{~(|.,-)"1@(=@i.@#,-)^:(<:`(,:@,&*-))

This evaluates to a verb that takes a number and returns a 2D character array. Try it online!

Explanation

I first construct a matrix of the values -1, 0 and 1 by iterating an auxiliary verb, and then replace the numbers by characters. The auxiliary verb constructs the right half of the next iteration, then mirrors it horizontally to produce the rest. In the following explanation, , concatenates 2D arrays vertically and 1D arrays horizontally.

' /\'{~(|.,-)"1@(=@i.@#,-)^:(<:`(,:@,&*-))  Input is n.
                          ^:(            )  Iterate this verb
                             <:             n-1 times
                               `(       )   starting from
                                    ,&*-    the array 1 -1 (actually sign(n), sign(-n))
                                 ,:@        shaped into a 1x2 matrix:
                                             Previous iteration is y.
                      #                      Take height of y,
                   i.@                       turn into range
                 =@                          and form array of self-equality.
                                             This results in the identity
                                             matrix with same height as y.
                       ,-                    Concatenate with -y, pad with 0s.
       (    )"1@(        )                   Then do to every row:
        |.,-                                 Concatenate reversal to negation.
' /\'{~                                     Finally index entry-wise into string.

Answer 6

JavaScript (ES6), 105 bytes

f=n=>n<2?"/\\":" "+f(n-1).split`/`[0].replace(/|/g,"$`$'$'/$`$`\\$'$'$` \n")+f(n-1).replace(/.*/g,"$&$&")

Works by building the result up recursively from the base case /\. The bottom half is just the previous case with each line duplicated. The top half was a little trickier; it looks as if you want to take the previous case and only keep the two sides but you also have to worry about padding the strings to double the width, so instead I do some regex magic. By taking the leading spaces from the previous case and splitting at every point, I can consider the spaces before and after that point. At each match the spaces before increase by 1 and the spaces after decrease by 1; this can be used to position the / and \ in the correct places. The newlines and padding are also added here; this takes care of all the padding except a trailing space on each line and a leading space on the first line which I have to add manually. (Leading spaces on subsequent lines come from the matched string).

Answer 7

Charcoal, 12 bytes

ＦＮ«→↗⌈Ｘ²⊖ι‖Ｍ

Try it online! Link is to verbose version of code. Explanation:

 Ｎ              Input as a number
Ｆ «             Loop over implicit range
   →            Move right (because mirroring moves the cursor)
         ι      Current index
        ⊖       Decremented
      Ｘ²        Power of 2
     ⌈          Ceiling
    ↗           Draw diagonal line
          ‖Ｍ    Mirror image

The line lengths are 1, 1, 2, 4, 8 ... 2^(N-2), thus the awkward calculation.

Answer 8

Stax, 20 19 bytes

≡mX░R○k╣∙╒ab^◘⌐╖x▼;

Run and debug it

Answer 9

Batch, 218 bytes

@echo off
set/a"n=1<<%1"
set s=set t=
%s%/\
set l=for /l %%i in (2,1,%n%)do call
%l% %s% %%t%% 
%l%:l
:l
echo %t%
set/an-=1,m=n^&n-1
%s%%t: /=/ %
%s%%t:\ = \%
if %m% neq 0 exit/b
%s%%t:/ =/\%
%s%%t: \=/\%

Note: Line 6 ends in a space. Works by moving the branches left and right appropriately each time, except on rows that are 2ⁿ from the end, in which case the branches get forked instead.

Answer 10

Haxe, 181 bytes

function g(n):String return(n-=2)==-1?"/\\":[for(y in 0...1<<n)[for(x in 0...4<<n)x+y+1==2<<n?"/":x-y==2<<n?"\\":" "].join("")].concat([for(y in g(n+1).split("\n"))y+y]).join("\n");

Or, with some optional whitespace:

function g(n):String
  return
    (n -= 2) == -1
    ? "/\\"
    : [ for (y in 0...1 << n)
        [ for (x in 0...4 << n)
          x + y + 1 == 2 << n
          ? "/"
          : x - y == 2 << n
            ? "\\"
            : " "
        ].join("")
      ].concat([ for (y in g(n + 1).split("\n"))
        y + y
      ]).join("\n");

I was working for a while on a solution which created an array of space characters of the right size first, then iteratively put the forked paths lower and lower (and more densely at each iteration). It remained 230+ bytes, though. The approach here is pretty much what @Laikoni's Haskell approach is. I couldn't get away with not having :String, because Haxe is not smart enough to identify that the return type will always be a String.

This is a function only, here's a full programme to test it:

class Main {
    public static function main(){
        function g(n):String return(n-=2)==-1?"/\\":[for(y in 0...1<<n)[for(x in 0...4<<n)x+y+1==2<<n?"/":x-y==2<<n?"\\":" "].join("")].concat([for(y in g(n+1).split("\n"))y+y]).join("\n");
        Sys.println(g(Std.parseInt(Sys.args()[0])));
    }
}

Put the above in Main.hx, compile with haxe -main Main.hx -neko frac.n and test with neko frac.n 4 (replace 4 with the desired order).

Answer 11

PHP, 188 Bytes

Online Version

function f($l,$r=0,$m=1){global$a;for(;$i<$l;$i++)$i<$l/2?$a[$i+$r]=str_repeat(str_pad("/".str_pad("",2*$i)."\\",2*$l," ",2),$m):f($l/2^0,$r+$l/2,2*$m);}f(2**$argv[1]/2);echo join("\n",$a);

Expanded

function f($l,$r=0,$m=1){
global$a;    
for(;$i<$l;$i++)    
$i<$l/2
    ?$a[$i+$r]=str_repeat(str_pad("/".str_pad("",2*$i)."\\",2*$l," ",2),$m)
    :f($l/2^0,$r+$l/2,2*$m);
}
f(2**$argv[1]/2);
echo join("\n",$a);