Print a non-clashing binary search tree 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&amp;Cs apply
This is code-golf. 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
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&gt;v)if(r==null)r=new N(n);else r.i(n);else if(n&lt;v)if(l==null)l=new N(n);else l.i(n);}void p(N node){a[b][h]=""+node.v;if(w[h]&lt;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&lt;b)a[++g][h]="|";h++;p(node.l);if(a[--g][--h].equals("|"))g--;}}void d(){for(e=-1;++e&lt;a.length;){o="";for(j=-1;++j&lt;a[0].length;){p=a[e][j];if(p!=null)if(p.equals("|")){for(i=0;i++&lt;w[j]-p.length()+2;)o+=" "; o+=p;}else for(i=0;i++&lt;w[j]+2;)o+=" ";else for(i=0;i++&lt;=w[j]+1;)o+=" ";}if(!o.trim().equals(""))System.out.println(o);o="";for(c=-1;++c&lt;a[0].length;){p=a[e][c];if(p!=null)if(p.equals("|")){for(i=0;i++&lt;w[c]-p.length()+2;)o+=" ";o+=p;}else{for(i=0;i++&lt;w[c]-p.length()+2;)o+="_"; o+=p; }else for(i=0;i++&lt;=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++&lt;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 &gt; index) {
        if (rightNode == null) {
            rightNode = new N(newValue);
        }
        else {
            rightNode.i(newValue);
        }
    }
    else if (newValue &lt; 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] &lt; 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&lt;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 &lt; nodes.length;) {
        // Sloppy. Inject extra rows to extend pipes (double spacing)
        line = "";
        for (int col = -1; ++col &lt; nodes[0].length;) {
            node = nodes[row][col];
            if (node!=null){
                if (node.equals("|")) {
                    for (loop=0; loop++&lt; colWidths[col] - node.length() + 2; ){
                        line+=" ";
                    }
                    line+=node;
                }
                else {
                    for (loop=0; loop++&lt; colWidths[col]  + 2;){
                        line+=" ";
                    }
                }
            }
            else {
                for (loop=0; loop++&lt;=colWidths[col]+1;){
                    line+=" ";
                }
            }
        }
        if (!line.trim().equals("")){
            System.out.println(line);
        }
        line="";

        for ( col = -1; ++col &lt; nodes[0].length;) {
            node = nodes[row][col];
            if (node!=null){
                if (node.equals("|")) {
                    for (loop=0; loop++&lt; colWidths[col] - node.length() + 2;){
                        line+=" ";
                    }
                    line+=node;
                }
                else {
                    for (loop=0; loop++&lt; colWidths[col] - node.length() + 2;){
                        line+="_";
                    }
                    line+=node;
                }
            }
            else {
                for (loop=0; loop++&lt;=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++&lt;values.length-1;)
    t.i(Integer.parseInt(values[i]));
    t.p(t);
    t.d();
}
}