Pretty Print Binary Tree

Question

I am working on the following code challenge:

PrintableTree is a simple Binary Search Tree with no balancing. It may contain int values that are added via the add method. The main challenge is to pretty print the tree via the prettyPrint method. This means that the whole tree should be converted to a String representing its inner structure from the smaller values to the greater ones. Also, you must use box-drawing characters to show node connections.

Example:

Elements: 123 11 200 1 100 150 2000

Pretty printed tree:

      ┌1
   ┌11┤
   │  └100
123┤
   │   ┌150
   └200┤
       └2000

Another example (of not so balanced tree):

Elements: 931 39 196 385 388 207 185 955 957 542 904 498 394

Pretty printed tree:

   ┌39┐
   │  │   ┌185
   │  └196┤
   │      │   ┌207
   │      └385┤
   │          └388┐
   │              │       ┌394
   │              │   ┌498┘
   │              └542┤
   │                  └904
931┤
   └955┐
       └957

Your class should implement this interface

public interface PrintableTree {

    void add(int i);
    String prettyPrint();

    static PrintableTree getInstance() {
        return new PrettyPrintableTree();
    }
}

I wrote this implementation:

public class PrettyPrintableTree implements PrintableTree {

    private static class Node {
        private final int data;
        private Node left = null;
        private Node right = null;

        public Node(int data) {
            this.data = data;
        }

        public int getSize() {
            return Integer.toString(data).length();
        }

    }

    private Node root = null;
    private StringBuilder mainSB = new StringBuilder();

    @Override
    public void add(int i) {
        root = add(root, i);
    }

    private Node add(Node node, int value) {
        if (node == null) {
            return new Node(value);
        } else if (value < node.data) {
            node.left = add(node.left, value);
        } else {
            node.right = add(node.right, value);
        }
        return node;
    }

    private void printSimple(Node node) {
        if (node != null) {
            printSimple(node.left);
            System.out.println(node.data);
            printSimple(node.right);
        }
    }

    @Override
    public String prettyPrint() {
        printTree(root,0, false);
        System.out.println(mainSB);
        return mainSB.toString();
    }

    private void printTree(Node node, int space, boolean isRight)
    {

        if (node == null) return;

        space += node.getSize() + 1;
        printTree(node.left, space, false);

        if (node == root) {
            space = space - root.getSize() - 1;
        }
        if (node == root.left) {
            space = root.getSize();
        }
        if (node == root.right) {
            space = root.getSize();
        }

        mainSB.append(" ".repeat(Math.max(0, space)));
        if (node.right == null && node.left == null) {
            if (node == root)
                mainSB.append(node.data).append("\n");
            else
                mainSB.append(isRight ? "└" : "┌").append(node.data).append("\n");
        }
        else if (node.right != null && node.left != null) {
            if (node == root)
                mainSB.append(node.data).append("┤").append("\n");
            else
                mainSB.append(isRight ? "└" : "┌").append(node.data).append("┤").append("\n");
        }
        else if (node.right == null) {
            if (node == root)
                mainSB.append(node.data).append("┘").append("\n");
            else
                mainSB.append(isRight ? "└" : "┌").append(node.data).append("┘").append("\n");
        }
        else {
            if (node == root)
                mainSB.append(node.data).append("┐").append("\n");
            else
                mainSB.append(isRight ? "└" : "┌").append(node.data).append("┐").append("\n");
        }

        printTree(node.right, space, true);

    }
}

But I have some problems:

I can't figure out how to add the "|" character so to connect nodes that are far apart in their vertical distance. There are some problems with the horizontal spacing as well.

You can see these problems in the following outputs produced by the above code:

Elements: 123 11 200 1 100 150 2000

         ┌1
   ┌11┤
       └100
123┤
        ┌150
   └200┤
        └2000

elements: 931 39 196 385 388 207 185 955 957 542 904 498 394

   ┌39┐
           ┌185
       └196┤
               ┌207
           └385┤
               └388┐
                           ┌394
                       ┌498┘
                   └542┤
                       └904
931┤
   └955┐
       └957

Answer 1

You could use a second StringBuilder to maintain what should appear on one line only, so you can keep track of vertical lines that should be drawn higher up (more left) in the tree.

Then extend the main StringBuilder with copies from that.

NB: I wouldn't use an instance variable for maintaining that StringBuilder. It seems better practice to use a local variable for that, passing it on as argument.

Here are the functions you could define:

    public void prettyPrint() {
        System.out.println(prettyString());
    }

    public String prettyString() {
        StringBuilder treeSB = new StringBuilder();
        prettyString(root, new StringBuilder("\n"), treeSB);
        return treeSB.substring(1); // Omit initial '\n'
    }

    private void prettyString(Node node, StringBuilder lineSB, StringBuilder treeSB)
    {
        if (node == null) return;

        int dataSize = node.getSize(); // Integer.toString(node.data).length();
        int depth = lineSB.length();
        int i = "\n │".indexOf(lineSB.charAt(depth - 1));
        int j = (node.left != null ? 2 : 0) + (node.right != null ? 1 : 0);
        
        lineSB.append(" ".repeat(dataSize + 1));
        prettyString(node.left, lineSB, treeSB);
        lineSB.setLength(depth - 1);
        
        treeSB.append(lineSB);
        treeSB.append("\n┌└".charAt(i));
        treeSB.append(node.data);
        treeSB.append(" ┐┘┤".charAt(j));

        lineSB.append("\n│ ".charAt(i));
        lineSB.append(" ".repeat(dataSize));
        lineSB.append(" │ │".charAt(j));
        prettyString(node.right, lineSB, treeSB);
    }