18
\$\begingroup\$

Inspired by a recent question on SO...

Write a function to print a binary tree in the following format:

   3
 /   \
1     5
 \   / \
  2 4   6
  1. The output should consist of a line of nodes, followed by a line of / and \ characters indicating relationships, followed by a line of nodes, etc.
  2. You can assume all nodes are representable as a single character.
  3. Adjacent nodes on the lowest level should be separated by at least one space, nodes further up should be separated as appropriate.
  4. Nodes with two children should be placed precisely in the middle of their direct children.
  5. Relationship slashes should be halfway between the parent and the appropriate child (round whichever way you want).

Input:

The input will be provided as an argument to your function. I won't specify the exact structure of the tree, however it must be usable as an actual binary tree. No "trees are represented in my program as strings coincidentally looking like the expected output".

You may print to an output stream or return a string containing the output, your choice.

Points for shortest code, but I'd much prefer a fully working long solution than a 90%-working short one.


Update for the bounty:

For the bounty, I (Optimizer) am making slight changes:

  • Input can be from STDIN,ARGV or function argument.
  • Output needs to be on STDOUT (or console.log for JS)
  • You can assume that input is in a form of array, for ex. [1,2,3] or [1 2 3]

Update 2 - The binary tree should actually be a binary search tree. Since I did not mention this initially, I will allow users to treat the converting a normal array into a binary search tree array as a separate program and the final byte count will only be for the program to take in the array as argument and print it like a binary tree.

\$\endgroup\$
  • \$\begingroup\$ Should we use several relationship slashes were appropriate? Must we use the minimum number of slashes? Should one distinguish between having a single left child and a single right child? Would it be fine to have leading spaces in every output line? \$\endgroup\$ – user475 Feb 11 '11 at 10:31
  • \$\begingroup\$ What do we do if the tree isn't complete (2^n-1 nodes for some n)? Some nodes (which ones?) have only one child. But if we're allowed to have nodes with only one child, the degenerate tree is easy to make (1-2-3-4-5-6 down and to the right, say). \$\endgroup\$ – Keith Randall Dec 16 '14 at 7:04
  • \$\begingroup\$ How you draw it for large numbers? For example 30000,1000,499999 \$\endgroup\$ – Mohsen Dec 17 '14 at 6:04
9
\$\begingroup\$

Fortran 77 -- 1085 characters

      subroutine q(u,t)
      implicit integer(i-z)
      character*33 f,g
      dimension t(u)
      m=ceiling(log(real(u))/log(2.))
      v=2**(m+1)-1
      do l=1,m
         n=2**(l-1)
         k=2**(m-l+2)-3
         w=(3+k)*2**(l-1)-k
         p=1+(v-w)/2
         if(l.ne.1)then
            write(f,'(A,I3,A)')'(A',p,',$)'
            print f,' '
            write(f,'(A5,I3,A3)')'(A3,A',k,',$)'
            do j=2**(l-1),2**l-1
               if(t(j/2).lt.0.or.t(j).lt.0)then
                  print f,'   ',' '
               elseif(mod(j,2).eq.0)then
                  print f,'  /',' '
               else
                  print f,' \ ',' '
               endif
            enddo
            print*
         endif
         write(f,'(A,I3,A)')'(A',p,',$)'
         print f,' '
         write(f,'(A5,I3,A3)')'(I3,A',k,',$)'
         write(g,'(A2,I3,A3)')'(A',k+3,',$)'
         do j=2**(l-1),2**l-1
            if(t(j).ge.0)then
               print f,t(j),' '
            else 
               print g,' '
            endif
         enddo
         print*
      enddo
      end

The tree is represented in the input array t in the usual fashion, root at 1, root->left at 2, root->right at 3 root->left->left at 4...

The output should fit in a conventional terminal up to 5 levels deep.

I use exactly one slash between each pair of nodes, which looks pretty silly near the top once there are four or more levels. I allowed for up to three digit nodes.

Full program with comments and a launching scaffold:

      program tree

      parameter (l=8)          ! How many nodes to support
      dimension i(l)

c     Initialize the array to all empty nodes
      do j=1,l
         i(j)=-1
      end do
c     Fill in some values
      i(1)=3
      i(2)=1
      i(3)=5
      i(5)=2
      i(6)=4
      i(7)=7
c      i(14)=6
c      i(15)=8
c     Call the printing routine
      call q(l,i)

      stop
      end

c     Print an ASCII representation of the tree
c
c     u the length of the array containing the tree
c     t an integer array representing the tree.
c
c     The array contains only non-negative values, and empty nodes are
c     represented in the array with -1.
c
c     The printed representation uses three characters for every node,
c     and places the (back) slash equally between the two node-centers.
      subroutine q(u,t)
      implicit integer(i-z)
      character*33 f,g
      dimension t(u)
      m=ceiling(log(real(u))/log(2.)) ! maximum depth of the tree
      v=2**(m+1)-1              ! width needed for printing the whole tree
                                ! Optimized from 3*2**m + 1*((2**m)-1) at
                                ! the bottom level
      do l=1,m
         n=2**(l-1)             ! number of nodes on this level
         k=2**(m-l+2)-3         ! internode spacing
         w=(3+k)*2**(l-1)-k     ! width needed for printing this row
                                ! Optimized from 3*2**l + k*((2**l)-1) at
                                ! the bottom level
         p=1+(v-w)/2            ! padding for this row
c     Print the connecting lines associated with the previous level
         if(l.ne.1)then         ! Write the connecting lines
            write(f,'(A,I3,A)')'(A',p,',$)'
            print f,' '
            write(f,'(A5,I3,A3)')'(A3,A',k,',$)'
            do j=2**(l-1),2**l-1
               if(t(j/2).lt.0.or.t(j).lt.0)then
                  print f,'   ',' '
               elseif(mod(j,2).eq.0)then
                  print f,'  /',' '
               else
                  print f,' \ ',' '
               endif
            enddo
            print*
         endif
c     Print the nodes on this level
         write(f,'(A,I3,A)')'(A',p,',$)'
         print f,' '
         write(f,'(A5,I3,A3)')'(I3,A',k,',$)'
         write(g,'(A2,I3,A3)')'(A',k+3,',$)'
         do j=2**(l-1),2**l-1
            if(t(j).ge.0)then
               print f,t(j),' '
            else 
               print g,' '
            endif
         enddo
         print*
      enddo
      end

Output with input equivalent to the example:

$ ./a.out 
         3             
     /      \      
     1       5     
      \    /  \  
       2   4   7 
\$\endgroup\$
  • \$\begingroup\$ HELP why this language? \$\endgroup\$ – tomsmeding Dec 15 '14 at 19:14
  • 9
    \$\begingroup\$ Because it is so poorly suited to golfing. \$\endgroup\$ – dmckee Dec 15 '14 at 19:16
5
+100
\$\begingroup\$

CJam, 100 99 bytes

q~_,2b,)2\#:Q1@{_2$<Q(S*:T*TQ2/:Q@ts[N+_0@{@1$' >{2$St2$_Q3*&2/^_4$>"\/"=t}*@)}/;U*o]o1:U$>\2*\}h];

Input must be a list of characters, without any ascii control characters. Empty nodes are denoted by a space. It also must be a perfect binary tree with exactly 2n-1 nodes.

Example:

['6 '3 '7 '1 '4 '  '9 '0 '2 '  '5 '  '  '8 ' ]

Or simply use strings:

"63714 902 5  8 "

Output:

                6              
            /       \          
        3               7      
      /   \               \    
    1       4               9  
   / \       \             /   
  0   2       5           8    

Explanation

q~                        " Read input. ";
_,2b,                     " Get tree height. ";
)2\#:Q                    " Get (displayed) tree width and save it in Q. ";
1@                        " Push X=1 and rotate the input to top. ";
{                         " Do: ";
    _2$<                  " Get first X characters from the input. ";
    Q(S*:T                " T = (Q-1) spaces. ";
    *                     " Separate the X characters by T. ";
    TQ2/:Q@t              " Put the string in the middle of T, and divide Q by 2. ";
    s                     " Concatenate everything into a string.
                            This is the line of node labels. ";
    [
        N+                " Append a newline. ";
        _                 " Duplicate. ";
        0@                " Push a 0 and rotate the original string to top. ";
        {                 " For each character: ";
            @             " Rotate the duplicate to top. ";
            1$' >         " Test if the current character is greater than a space. ";
            {             " If true: ";
                2$St      " Set the current character in the duplicate to space. ";
                2$        " Copy the current position I (the number initialized with 0). ";
                _Q3*&2/^  " Calculate I ^ ((I & (3*Q))>>1),
                            the position of the relationship character. ";
                _4$>      " Test if it is greater than the current position. ";
                "\/"=     " Select the relationship character. ";
                t         " Change the character in the duplicate. ";
            }*
            @)            " Increment the current position. ";
        }/
                          " The last two items are the line of relationship characters
                            and the tree width. ";
        ;                 " Discard the tree width. ";
        U*                " If it is the first line, empty the line of
                            relationship characters. ";
        o                 " Output. ";
    ]o                    " Output the line of node labels. ";
    1:U                   " Mark it not the first line. ";
    $>                    " Remove the first X characters from the input. ";
    \2*\                  " Multiply X by 2. ";
}h                        " ...while the input is not empty. ";
];                        " Discard everything in the stack. ";

Conversion script

[[0LL]W]
[q~{_a_:i={'0+}*}%La2*f+
_,,]z$
1$a+
{
    {
        1$1=1$1=>:T
        {
            ~@0=2 3$1=t
            @1@ta\+
        }*
        T
    }g
}*
0=1=a
{
    {
        (M\+:M;
        La[' LL]aer~
    }%
    _[' LL]a-
}g
];
M0+`-3<']+

It accepts either characters or single digit numbers.

Examples (all are the same):

['6 '7 '9 '3 '1 '2 '8 '4 '0 '5]
[6 7 9 3 1 2 8 4 0 5]
"6793128405"

Output:

['6 '3 '7 '1 '4 ' '9 '0 '2 ' '5 ' ' '8 ' ]

It's a straight-forward Cartesian tree construction.

\$\endgroup\$
  • \$\begingroup\$ You can just add two more bytes and make the input of conversion script as proper integers instead of characters :) \$\endgroup\$ – Optimizer Dec 21 '14 at 15:49
  • \$\begingroup\$ @Optimizer Edited to support both. I think characters makes more sense since it only support node names with a single character. There are much more characters than single digit numbers. \$\endgroup\$ – jimmy23013 Dec 21 '14 at 15:59
2
\$\begingroup\$

Python 2, 411 bytes

import math
def g(a,o,d,l,b):
 if l<0:
    return
 c=2*b+1
 k=2*l+1
 o[k]=' '*b
 n=d-l
 p=1 if n==0 else 3*2**n-1
 o[k-1]=p/2*' '
 i=0
 for v in a[2**l-1:2**l*2-1]:
    v=' ' if v==None else v
    o[k]+=v+' '*c
    m=' ' if v==' ' else '/' if i%2==0 else '\\'
    o[k-1]+=m+max(1,b)*' ' if i%2==0 else m+p*' '
    i+=1

 g(a,o,d,l-1,c)
def f(a):
 d=int(math.log(len(a),2))
 o=['']*(d*2+2)
 g(a,o,d,d,0)
 print '\n'.join(o[1:])

Note: First indentation level is 1 space, second is one tab.

Call f with a list of one-character strings or None's, eg. f(['1',None,'3']). The list can't be empty.

This should obey the rules for the bounty.

Converter script:

Converts and array to the format used by the binary tree printer. Example:

$ python conv.py [3,5,4,6,1,2]
['3', '1', '5', None, '2', '4', '6']

-

import sys

def insert(bt, i):
    if i < bt[0]:
        j = 0
    else:
        j = 1

    n = bt[1][j]
    if n == [None]:
        bt[1][j] = [i, [[None], [None]]]
    else:
        insert(bt[1][j], i)

def insert_empty(bt, i):
    if i == 0:
        return
    if bt == [None]:
        bt += [[[None], [None]]]

    insert_empty(bt[1][0], i - 1)
    insert_empty(bt[1][1], i - 1)

def get(l, level):
    if level == 0:
        if type(l) == list:
            return ([], l)
        else:
            return ([l], [])
    elif type(l) != list:
        return ([], [])

    res = []
    left = []

    for r, l in  [get(i, level - 1) for i in l]:
        res += r
        left += l

    return (res, left)

if __name__ == '__main__':
    l = eval(sys.argv[1])
    bt = [l[0], [[None], [None]]]
    map(lambda x: insert(bt, x), l[1:])

    depth = lambda l: 0 if type(l) != list else max(map(depth, l)) + 1
    d = (depth(bt) + 1) / 2

    insert_empty(bt, d - 1)

    flat = []
    left = bt
    i = 0
    while len(left) > 0:
        f, left = get(left, 1)
        flat += f

        i += 1

    for i in range(len(flat) - 1, -1, -1):
        if flat[i] == None:
            flat.pop()
        else:
            break

    flat = map(lambda x: None if x == None else str(x), flat)

    print flat

Examples:

To run these you should have the main file named bt.py and the converter file named conv.py.

$ python conv.py [3,5,4,6,1,2] | python -c 'import bt; bt.f(input())'
   3
  / \
 1   5
  \ / \
  2 4 6
$ python conv.py [5,4,3,7,9] | python -c 'import bt; bt.f(input())'
   5
  / \
 4   7
/     \
3     9
$ python conv.py [1,2,3,4,5,6] | python -c 'import bt; bt.f(input())'
                               1
                                       \
                                               2
                                                   \
                                                       3
                                                         \
                                                           4
                                                            \
                                                             5
                                                              \
                                                              6
$ python conv.py [6,5,4,3,2,1] | python -c 'import bt; bt.f(input())'
                                   6
                       /
               5
           /
       4
     /
   3
  /
 2
/
1
\$\endgroup\$
  • \$\begingroup\$ You are not actually creating the binary tree. Just printing the array as a binary tree. The output of ['1','2','3','4','5','6','7','8','9'] array is not what you showed. It should have 3 as a right child of 2 which is a right child of 1 which is a root element. \$\endgroup\$ – Optimizer Dec 18 '14 at 11:44
  • \$\begingroup\$ @Optimizer From the question: "The input will be provided as an argument to your function. I won't specify the exact structure of the tree, however it must be usable as an actual binary tree." I don't see a specific definition of the array format used. \$\endgroup\$ – Tyilo Dec 18 '14 at 17:24
  • \$\begingroup\$ The question originally is about printing a binary tree. Your outputs are not binary trees. Format of the array has nothing to do with it. \$\endgroup\$ – Optimizer Dec 18 '14 at 17:29
  • \$\begingroup\$ @Optimizer how are they not binary trees? From Wikipedia: a binary tree is a tree data structure in which each node has at most two children. Do any of the nodes have more than two children? \$\endgroup\$ – Tyilo Dec 18 '14 at 17:52
  • \$\begingroup\$ Ughh. I see now. I think there is a term misunderstanding here . Even in the initial examples, the output is of the format of binary search tree. And my bounty is also for a binary search tree only. Sorry for the confusion there. \$\endgroup\$ – Optimizer Dec 18 '14 at 18:03
1
\$\begingroup\$

APL, 125 characters

{⍵{x←⍵[0;d←⌈2÷⍨1⌷⍴⍵]←↑⍺
2 1∇{x[2↓⍳↑⍴x;(⍳d)+d×⍺-1]←⍵(⍺⍺⍣t←0≠⍴⍵)2↓x[;⍳d]
x[1;d+(⌈d÷4)ׯ1*⍺]←' /\'[t×⍺]}¨⍺[2 1]
x}' '⍴⍨2(×,*)≡⍵}

Example:

{⍵{x←⍵[0;d←⌈2÷⍨1⌷⍴⍵]←↑⍺
2 1∇{x[2↓⍳↑⍴x;(⍳d)+d×⍺-1]←⍵(⍺⍺⍣t←0≠⍴⍵)2↓x[;⍳d]
x[1;d+(⌈d÷4)ׯ1*⍺]←' /\'[t×⍺]}¨⍺[2 1]
x}' '⍴⍨2(×,*)≡⍵}('1' ('2' ('3' ('4' ()()) ('5' ()())) ('6' ()('7' ()())))('8' ()('9' ('0' ()())())))

Tested here.

\$\endgroup\$
  • \$\begingroup\$ Is this the conversion script too ? \$\endgroup\$ – Optimizer Dec 20 '14 at 21:56
  • \$\begingroup\$ @Optimizer It takes the nested array input format, which can be probably used as binary search tree (but I'm not sure about the complexity). If I must use some more usual formats... maybe I'll do it later. \$\endgroup\$ – jimmy23013 Dec 20 '14 at 22:14
  • \$\begingroup\$ @Optimizer Now reading the question again, does "binary search tree array" means the array of a complete binary tree in depth order (or something else)? I didn't think it was anything specific. And searching this term didn't give anything useful. \$\endgroup\$ – jimmy23013 Dec 20 '14 at 22:22
  • \$\begingroup\$ en.wikipedia.org/wiki/Binary_tree#Arrays \$\endgroup\$ – Optimizer Dec 20 '14 at 22:28
  • \$\begingroup\$ @Optimizer Well, that was just what I meant. But I don't think it is usually called "binary search tree array", but only "a kind of array storage of binary trees". It probably need some clarification... And I'll probably fix this answer days later, maybe in another language... \$\endgroup\$ – jimmy23013 Dec 20 '14 at 22:37
0
\$\begingroup\$

Ruby, 265 bytes

def p(t);h=Math.log(t.length,2).to_i;i=-1;j=[];0.upto(h){|d|s=2**(h-d)-1;c=2**d;if d>0;m=' '*(s+s/2)+'I'+' '*(s-s/2);1.upto(d){m+=' '+m.reverse};w=i;puts m.gsub(/I/){|o|t[w+=1]?(w%2==0?'\\':'/'):' '};end;puts (0...c).map{' '*s+(t[i += 1]or' ').to_s+' '*s}*' ';};end

The @proudhaskeller version, 269 bytes

def p(t);h=Math.log(t.length,2).to_i;i=-1;j=[];0.upto(h){|d|s=(z=2**(h-d))-1;c=2**d;if d>0;m=' '*(s+z/2)+'I'+' '*(s-z/2);1.upto(d){m+=' '+m.reverse};w=i;puts m.gsub(/I/){|o|t[w+=1]?(w%2==0?'\\':'/'):' '};end;puts (0...c).map{' '*s+(t[i += 1]or' ').to_s+' '*s}*' ';};end

Explaination

The verbose version:

def p(t)
  depth = Math.log(t.length, 2).floor
  i = -1
  j = []
  (0..depth).each do |d|
    s = 2 ** (depth-d)-1
    c = 2 ** d

    if d > 0
      m = ' '*(s+s/2) + '|' + ' '*(s-s/2)
      w = i
      1.upto(d) { m += ' ' + m.reverse }
      puts m.gsub(/\|/) { |o| t[w+=1] ? (w%2==0 ? '\\' : '/') : ' ' }
    end

    puts (0...c).map{' '*s+(t[i += 1]or' ').to_s+' '*s}*' '
  end
end

Example

n = nil
p([
  1, 2, 3, 4, 5,
  n, 7, 8, 9, 0,
  1, n, n, 4, 5,
  6, 7, 8, 9, 0,
  1, 2, 3, n, n,
  n, n, 8, 9, n,
  n
])

gives:

               1               
          /         \          
       2               3       
    /     \               \    
   4       5               7   
 /   \   /   \           /   \ 
 8   9   0   1           4   5 
/ \ / \ / \ / \         / \    
6 7 8 9 0 1 2 3         8 9   

(I haven't written the conversion script yet.)

\$\endgroup\$
  • \$\begingroup\$ your slashes aren't exactly in the middle \$\endgroup\$ – proud haskeller Dec 22 '14 at 9:46
  • \$\begingroup\$ @proudhaskeller "round whichever way you want", I thought it looks cooler this way. You can replace s/2 with (s+1)/2 if you want. \$\endgroup\$ – AlexRath Dec 22 '14 at 12:04
  • \$\begingroup\$ No, the slashes in the first row aren't exactly in he middle, in this row this isn't a matter of rounding \$\endgroup\$ – proud haskeller Dec 22 '14 at 12:07
  • \$\begingroup\$ @proudhaskeller If you replace s/2 with (s+1)/2 they are exactly in the middle, but I still prefer this way because it makes the leftmost and rightmost branches look round. \$\endgroup\$ – AlexRath Dec 22 '14 at 15:45
  • \$\begingroup\$ it is against the spec... \$\endgroup\$ – proud haskeller Dec 22 '14 at 16:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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