Print a non-clashing binary search tree

Question

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

• Martin Ender: Related.
• Denham Coote: @MartinBüttner yup, that's the one I was trying to be different enough from!
• Denham Coote: Is this challenge too simple? Boring? Trivial? Uninteresting? Would appreciate some feedback so I can pose better challenges.
• Martin Ender: 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.
• Denham Coote: 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.

Answer 1

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