Print binary search tree using text

Question

I want to print a binary search tree in this format:

     4 
    / \
   /   \
  2     5 
 / \   / \
1   3 4   6

I think I have to get the depth of the tree and, then, for each level, print a number of spaces before and after each element.

public void printTree(BSTNode T, int depth) {
    for (int i = 1; i <= depth; i++){
        //then what?
    }

I do not know how to proceed.

The node class:

public class BSTNode {
    private int value;
    private BSTNode left;
    private BSTNode right;

    public BSTNode(){
        value = 0;
        left = null;
        right = null;
    }

    public BSTNode(int x){
        value = x;
        left = null;
        right = null;
    }

    void setValue(int x){
        value = x;
    }

    int getValue(){
        return value;
    }

    void setLeft(BSTNode l){
        left = l;
    }

    BSTNode getLeft(){
        return left;
    }

    void setRight(BSTNode r){
        right = r;
    }

    BSTNode getRight(){
        return right;
    }
}

Answer 1

I have been able to find a solution without the slashes. Traverse the tree breadth-first; store all the values found on a level in an ArrayList; print the values on a line with indentation and spacing depending on the level; go to the next level and store all the values of the level, and so on.

The commented block is for the slashes.

Given the input 10, 5, 15, 1, 7, 20, 12, 6, 2, 8 into the binary search tree, the output without the slashes is

       10               
   5       15       
 1   7   12   20   
  2 6 8         

and with the slashes is

       10               
       / \       
      /   \      
     /     \     
    /       \    
   5       15       
   / \      / \   
  /   \    /   \  
 1   7   12   20   
 / \  / \  / \  / \ 
  2 6 8         

The output for the solution with the slashes is not perfect and needs improvement. There are some problems with the spacing between the nodes.

public void printTree(BSTNode T, int depth) {
    int indent, spacing, numberOfSlashes;
    ArrayList value = new ArrayList();
    for (int d = 1; d <= depth; d++){
        value.clear();
        getLevel(value, T, d);
        indent = (int) (Math.pow(2, (depth-d)) - 1);
        spacing = (int) (Math.pow(2, (depth-d+1)) - 1);
        for (int i = 0; i < indent; i++){
            System.out.print(" ");
        }
        for (Object x: value){
            System.out.print(x);
            for (int i = 0; i < spacing; i++){
                System.out.print(" ");
            }
        }
        System.out.println();
        /*if (depth != d){
            numberOfSlashes = (int) Math.pow(2, (depth-d-1));
            printSlash(value, numberOfSlashes, indent, 1);
        }*/
    }
}

private void printSlash(ArrayList v, int slashes, int indent, int s) {
    for (int z = 0; z < slashes; z++){
        for (int index = 0; index < v.size(); index++){
            for (int i = 0; i < indent; i++){
                System.out.print(" ");
            }
            System.out.print("/");
            for (int space = 0; space < s; space++){
                System.out.print(" ");
            }
            System.out.print("\\");
            for (int nextSpace = 0; nextSpace < indent; nextSpace++){
                System.out.print(" ");
            }
        }
        System.out.println();
        indent = indent - 1;
        s = s + 2;
    }
}

private void getLevel(ArrayList v, BSTNode T, int l) {
    if (T == null)
        v.add(" ");
    else if (l == 1)
        v.add(T.getValue());
    else if (l > 1){
        getLevel(v, T.getLeft(), l-1);
        getLevel(v, T.getRight(), l-1);
    }
}   

Answer 2

One thing's for sure: this is not an easy problem. Here's my approach.

First things first, let's get the recursion straight. What I'd like to be able to do is print the left subtree of the node, then print the right subtree, then somehow combine those two to get my final result. To do this, I'm going to need a data class for those intermediate values:

public class TreeString {
    private List<String> lines;
    private int columnCount;
    private int rootColumn;

    public TreeString(List<String> lines, int columnCount, int rootColumn) {
        this.lines = new ArrayList<>(lines);
        this.columnCount = columnCount;
        this.rootColumn = rootColumn;
    }

    /** @return the number of lines */
    public int getLineCount() {
        return lines.size();
    }

    /** @return the number of columns */
    public int getColumnCount() {
        return columnCount;
    }

    /** @return the index of the column containing the center of the root */
    public int getRootColumn() {
        return rootColumn;
    }

    /** @return the number of columns to the right of the column containing the center of the root */
    public int getRootColumnFromRight() {
        return getColumnCount() - (getRootColumn() + 1);
    }

    /** @return the line at {@code index} */
    public String getLine(int index) {
        return lines.get(index);
    }
}

So, for instance, this tree

    4
   / \
  2   5
 / \
1   3

would be represented by this TreeString:

lines = new ArrayList<>(Arrays.asList("    4  ", "   / \\ ", "  2   5", " / \\   ", "1   3  "));
columnCount = 7;
rootColumn = 4;

Notice that all lines have the same length. This will be important later on.

OK, so how do we implement printTree? Well, it's very simple: we kill the Batman write some boilerplate.

public void printTree(BSTNode node, int depth) {
    if (depth > 0) {
        TreeString treeString = treeStringFromBSTNode(node, depth);
        for (int i = 0; i < treeString.getLineCount(); ++i) {
            System.out.println(treeString.getLine(i));
        }
    }
}

public TreeString treeStringFromString(String string) {
    return new TreeString(Collections.singletonList(string), string.length(), string.length() / 2);
}

public TreeString treeStringFromBSTNode(BSTNode node, int depth) {
    TreeString value = treeStringFromString(String.valueOf(node.getValue()));
    TreeString left = depth <= 1 || node.getLeft() == null ? null : treeStringFromBSTNode(node.getLeft(), depth - 1);
    TreeString right = depth <= 1 || node.getRight() == null ? null : treeStringFromBSTNode(node.getRight(), depth - 1);
    return combineTreeStrings(value, left, right);
}

Now, on to the main event:

public String spaces(int numSpaces) {
    String string = "";
    for (int i = 0; i < numSpaces; ++i) {
        string += " ";
    }
    return string;
}

public TreeString combineTreeStrings(TreeString parent, TreeString left, TreeString right) {
    if (left == null && right == null) {
        return parent;
    }

    // the number of lines between the bottom of parent and the tops of left and right
    // also the number of columns between parent's root column and the root columns of left or right
    int verticalGap = 1;
    // the number of columns between the left end of right and the right end of left
    int middleGap =  0;
    if (left != null && right != null) {
        verticalGap = Math.max(verticalGap, (left.getRootColumnFromRight() + 1 + right.getRootColumn()) / 2);
        middleGap = (verticalGap - left.getRootColumnFromRight()) + 1 + (verticalGap - right.getRootColumn());
    }

    // the number of columns between the left end of left (or right, if left is null) and the left end of the result
    int lowerLeftGap;
    // the number of columns between the left end of parent and the left end of the result
    int upperLeftGap;
    if (left != null) {
        lowerLeftGap = Math.max(0, parent.getRootColumn() - verticalGap - 1 - left.getRootColumn());
        upperLeftGap = Math.max(0, left.getRootColumn() + 1 + verticalGap - parent.getRootColumn());
    } else {
        lowerLeftGap = Math.max(0, parent.getRootColumn() + 1 + verticalGap - right.getRootColumn());
        upperLeftGap = Math.max(0, right.getRootColumn() - verticalGap - 1 - parent.getRootColumn());
    }

    // the number of columns between the right end of the result and the right end of right (or left, if right is null)
    int lowerRightGap;
    // the number of columns between the right end of the result and the right end of parent
    int upperRightGap;
    if (right != null) {
        lowerRightGap = Math.max(0, -right.getRootColumnFromRight() - 1 - verticalGap + parent.getRootColumnFromRight());
        upperRightGap = Math.max(0, -parent.getRootColumnFromRight() + verticalGap + 1 + right.getRootColumnFromRight());
    } else {
        lowerRightGap = Math.max(0, -left.getRootColumnFromRight() + verticalGap + 1 + parent.getRootColumnFromRight());
        upperRightGap = Math.max(0, -parent.getRootColumnFromRight() - 1 - verticalGap + left.getRootColumnFromRight());
    }

    List<String> lines = new ArrayList<>();
    // parent lines
    for (int i = 0; i < parent.getLineCount(); ++i) {
        lines.add(spaces(upperLeftGap) + parent.getLine(i) + spaces(upperRightGap));
    }
    // slash and backslash lines
    for (int i = 0; i < verticalGap; ++i) {
        String leftLeg;
        if (left != null) {
            leftLeg = "/";
        } else if (upperLeftGap > 0) {
            leftLeg = " ";
        } else {
            leftLeg = "";
        }

        String rightLeg;
        if (right != null) {
            rightLeg = "\\";
        } else if (upperRightGap > 0) {
            rightLeg = " ";
        } else {
            rightLeg = "";
        }

        int numLeftSpaces = upperLeftGap + parent.getRootColumn() - leftLeg.length() - i;
        int numRightSpaces = upperRightGap + parent.getRootColumnFromRight() - rightLeg.length() - i;
        lines.add(spaces(numLeftSpaces) + leftLeg + spaces(i + 1 + i) + rightLeg + spaces(numRightSpaces));
    }
    // left and right lines
    for (int i = 0; i < Math.max(left == null ? 0 : left.getLineCount(), right == null ? 0 : right.getLineCount()); ++i) {
        String leftLine;
        if (left == null) {
            leftLine = "";
        } else if (i >= left.getLineCount()) {
            leftLine = spaces(left.getColumnCount());
        } else {
            leftLine = left.getLine(i);
        }

        String rightLine;
        if (right == null) {
            rightLine = "";
        } else if (i >= right.getLineCount()) {
            rightLine = spaces(right.getColumnCount());
        } else {
            rightLine = right.getLine(i);
        }

        lines.add(spaces(lowerLeftGap) + leftLine + spaces(middleGap) + rightLine + spaces(lowerRightGap));
    }
    return new TreeString(lines, upperLeftGap + parent.getColumnCount() + upperRightGap, upperLeftGap + parent.getRootColumn());
}

Hopefully this solves your problem! If there's any way this can be cleaned up, don't hesitate to comment.

Answer 3

What you can do is to take a queue and initialize it with nodes at each level as you go down traversing at each level. After that pop each element , print it and push to queue its left and right node. Like this go on traversing till entire depth and you shall be able to print the tree in your desired format.