7
\$\begingroup\$

Brief

  • Print an ASCII representation of a binary search tree.
  • You should write your own minimum implementation logic of a BST (node, left, right, insert)
(50,30,70,20,80,40,75,90) gives:

__50__70__80__90
   |       |
   |       |__75
   |
   |__30__40
       |
       |__20

Detailed requirements

  • Items are inserted into the tree in the order in which they are in the list
  • All node values are right aligned in columns.
  • Right nodes are joined using __
  • Right nodes are represented along the horizontal and appear directly to the right of the parent node
  • Right nodes are separated by a minimum of 2 underscores (__)
  • Left nodes are joined using | and |__ on the next line
  • Left nodes are represented along the vertical and appear under and to the right of the parent (ie, next column).
  • Left nodes are separated by a a minimum of a blank line (discounting pipes (|) linking child to parent)
  • The vertical pipes joining 2 left nodes should be in the column directly under the last character of the parent node (see samples)
  • Column width is determined using something like max(col_values[]).toString().length() + 2
  • Branching left always adds a new row to the tree diagram
  • 2 separate (left) branches never appear on the same line (right__right__right is OK)
  • The root node may optionally be prefixed with __ (Removing it just about doubled my test code!)
  • Input is a set of positive and/or negative integers
  • You do not need to deal with duplicate values (drop/ignore them)
  • I'm not placing many restrictions on trailing whitespaces:
    • You may have trailing whitespaces after the last node on a line
    • You may have trailing whitespace after a | on the empty lines
    • No whitespace between nodes when when branching right
  • Standard loopholes and T&Cs apply
  • This is . Shortest code in bytes wins!

I'm aware that this is a potential duplicate, but I think I've been specific enough in my requirements that it should pose new challenges.

Sample Input/Output

  • Input

    (50,40,30,20,10)
    
  • Output

    __50
       |
       |__40
           |
           |__30
               |
               |__20
                   |
                   |__10
    
  • Input

    (10,20,30,40,50)
    
  • Output

    __10__20__30__40__50
    
  • Input

    (50,700,30,800,60,4,5,10,20,2,500,850,900,950,870,35,1,-10)
    
  • Output

    __50__700__800__850__900__950
       |    |              |
       |    |              |__870
       |    |
       |    |___60__500
       |
       |___30___35
            |
            |____4____5___10___20
                 |
                 |____2
                      |
                      |____1
                           |
                           |__-10
    
\$\endgroup\$
5
  • 2
    \$\begingroup\$ Related. \$\endgroup\$ Aug 12, 2015 at 16:07
  • \$\begingroup\$ @MartinBüttner yup, that's the one I was trying to be different enough from! \$\endgroup\$ Aug 12, 2015 at 16:29
  • \$\begingroup\$ Is this challenge too simple? Boring? Trivial? Uninteresting? Would appreciate some feedback so I can pose better challenges. \$\endgroup\$ Sep 21, 2015 at 13:18
  • 1
    \$\begingroup\$ I don't think it's any of those. If anything the challenge is fairly hard. That's not a bad thing though, but it can mean that it receives less attention. \$\endgroup\$ Sep 21, 2015 at 13:30
  • \$\begingroup\$ Hmm. Didn't think it was too hard - perhaps it's the nature of the problem. Some challenges seem (to me, at least) to be far more complicated and they receive a few answers. No problem though. I enjoyed writing it and having to solve it too. Good exercise for myself. \$\endgroup\$ Sep 21, 2015 at 13:34

1 Answer 1

1
\$\begingroup\$

Java 1286 1106 1100 bytes

Here's an easy entry to beat ;-)

Pretty messy. I traverse the tree, populating a 2d array with the node values (and left branch pipes), and a size array with the maximum column widths. Then print the node array using size array to determine correct horizontal spacing. I look forward to seeing a better way of doing this.

class N{N l,r;int v,i,h,g,b,e,c,j;String[][]a=new String[10][10];int[]w=new int[10];String o="",p="";N(int x){v=x;}void i(int n){if(n>v)if(r==null)r=new N(n);else r.i(n);else if(n<v)if(l==null)l=new N(n);else l.i(n);}void p(N node){a[b][h]=""+node.v;if(w[h]<a[b][h].length())w[h]=a[b][h].length();if(node.r!=null){h++;p(node.r);h--;}if(node.l!=null){b++;while(g<b)a[++g][h]="|";h++;p(node.l);if(a[--g][--h].equals("|"))g--;}}void d(){for(e=-1;++e<a.length;){o="";for(j=-1;++j<a[0].length;){p=a[e][j];if(p!=null)if(p.equals("|")){for(i=0;i++<w[j]-p.length()+2;)o+=" "; o+=p;}else for(i=0;i++<w[j]+2;)o+=" ";else for(i=0;i++<=w[j]+1;)o+=" ";}if(!o.trim().equals(""))System.out.println(o);o="";for(c=-1;++c<a[0].length;){p=a[e][c];if(p!=null)if(p.equals("|")){for(i=0;i++<w[c]-p.length()+2;)o+=" ";o+=p;}else{for(i=0;i++<w[c]-p.length()+2;)o+="_"; o+=p; }else for(i=0;i++<=w[c]+1;)o+=" ";}if(!o.trim().equals(""))System.out.println(o);}}public static void main(String[]a){String[]q=a[0].split(",");N t=new N(Integer.parseInt(q[0]));for(int i=0;i++<q.length-1;)t.i(Integer.parseInt(q[i]));t.p(t);t.d();}}
__50__700__800__850__900__950        
   |    |              |             
   |    |              |__870        
   |    |                            
   |    |___60__500                  
   |                                 
   |___30___35                       
        |                            
        |____4____5___10___20        
             |                       
             |____2                  
                  |                  
                  |____1             
                       |             
                       |__-10        

Ungolfed

class N {
    N leftNode, rightNode;
    int index, loop, curRight, curDown, maxDown, row,col;
    String[][] nodes = new String[10][10]; 
    int[] colWidths = new int[10];
    String line = "", node="";

N(int index) { this.index = index; } void i(int newValue) { if (newValue > index) { if (rightNode == null) { rightNode = new N(newValue); } else { rightNode.i(newValue); } } else if (newValue < index) { if (leftNode == null) { leftNode = new N(newValue); } else { leftNode.i(newValue); } } } void p(N node) { // Push current node nodes[maxDown][curRight] = ""+node.index; // Keep track of max column widths if (colWidths[curRight] < nodes[maxDown][curRight].length()) { colWidths[curRight] = nodes[maxDown][curRight].length(); } // Branch right if (node.rightNode != null) { curRight++; p(node.rightNode); curRight--; } // Branch left if (node.leftNode != null) { maxDown++; while (curDown<maxDown){ nodes[++curDown][curRight] = "|"; } curRight++; p(node.leftNode); if (nodes[--curDown][--curRight].equals("|")) { //following the ladder back up curDown--; } } } void d() { for ( row = -1; ++row < nodes.length;) { // Sloppy. Inject extra rows to extend pipes (double spacing) line = ""; for (int col = -1; ++col < nodes[0].length;) { node = nodes[row][col]; if (node!=null){ if (node.equals("|")) { for (loop=0; loop++< colWidths[col] - node.length() + 2; ){ line+=" "; } line+=node; } else { for (loop=0; loop++< colWidths[col] + 2;){ line+=" "; } } } else { for (loop=0; loop++<=colWidths[col]+1;){ line+=" "; } } } if (!line.trim().equals("")){ System.out.println(line); } line=""; for ( col = -1; ++col < nodes[0].length;) { node = nodes[row][col]; if (node!=null){ if (node.equals("|")) { for (loop=0; loop++< colWidths[col] - node.length() + 2;){ line+=" "; } line+=node; } else { for (loop=0; loop++< colWidths[col] - node.length() + 2;){ line+="_"; } line+=node; } } else { for (loop=0; loop++<=colWidths[col]+1;){ line+=" "; } } } if (!line.trim().equals("")){ System.out.println(line); } } } public static void main(String[]a){ String[] values = a[0].split(","); N t=new N(Integer.parseInt(values[0])); for (int i=0;i++<values.length-1;) t.i(Integer.parseInt(values[i])); t.p(t); t.d(); } }
\$\endgroup\$

Your Answer

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

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