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

• Related. – Martin Ender Aug 12 '15 at 16:07
• @MartinBüttner yup, that's the one I was trying to be different enough from! – Denham Coote Aug 12 '15 at 16:29
• Is this challenge too simple? Boring? Trivial? Uninteresting? Would appreciate some feedback so I can pose better challenges. – Denham Coote Sep 21 '15 at 13:18
• 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. – Martin Ender Sep 21 '15 at 13:30
• 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. – Denham Coote Sep 21 '15 at 13:34

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