PrettyPrint a Binary Tree (Follow Up)

Question

I have improved the Pretty Printing of binary tree that I implemented previously. In this follow up I have made changes such that every tree is printed (not just a Complete binary tree).

Here is my changed implementation. Please suggest any improvements that are required.

public class PrettyPrintTree {

    public TreeNode root;

    public PrettyPrintTree(List<Integer> list) {
        root = createTree(list);
    }

    public static class TreeNode {
        TreeNode left;
        TreeNode right;
        int value;

        public TreeNode(int value) {
            this.value = value;
        }
    }

    public static TreeNode createTree(List<Integer> list) {
        TreeNode root = null;
        TreeNode temp, temp2;
        for (Integer integer : list) {
            if (root == null) {
                root = new TreeNode(integer);
                root.left = null;
                root.right = null;
                continue;
            }
            temp = root;
            temp2 = root;
            while (temp != null) {
                temp2 = temp;
                temp = (temp.value < integer) ? temp.right : temp.left;
            }

            if (temp2.value < integer) {
                temp2.right = new TreeNode(integer);
            } else {
                temp2.left = new TreeNode(integer);
            }
        }

        return root;
    }

    private static int getMaximumHeight(TreeNode node) {
        if (node == null)
            return 0;
        int leftHeight = getMaximumHeight(node.left);
        int rightHeight = getMaximumHeight(node.right);
        return (leftHeight > rightHeight) ? leftHeight + 1 : rightHeight + 1;
    }

    private static String multiplyString(String string, int times) {
        StringBuilder builder = new StringBuilder(string.length() * times);
        for (int i = 0; i < times; ++i) {
            builder.append(string);
        }
        return builder.toString();
    }

    public static String getStartingSpace(int height) {
        return multiplyString("  ", ((int) Math.pow(2, height - 1)) / 2);
    }

    public static String getUnderScores(int height) {
        int noOfElementsToLeft = ((int) Math.pow(2, height) - 1) / 2;
        int noOfUnderScores = noOfElementsToLeft
                - ((int) Math.pow(2, height - 1) / 2);

        return multiplyString("__", noOfUnderScores);
    }

    public static String getSpaceBetweenTwoNodes(int height) {
        if (height == 0)
            return "";

        int noOfNodesInSubTreeOfNode = ((int) Math.pow(2, height - 1)) / 2;
        /** Sum of spaces of the subtrees of nodes + the parent node */
        int noOfSpacesBetweenTwoNodes = noOfNodesInSubTreeOfNode * 2 + 1;

        return multiplyString("  ", noOfSpacesBetweenTwoNodes);
    }

    public static void printNodes(List<TreeNode> queueOfNodes,
            int noOfNodesAtCurrentHeight, int height) {
        StringBuilder nodesAtHeight = new StringBuilder();

        String startSpace = getStartingSpace(height);
        String spaceBetweenTwoNodes = getSpaceBetweenTwoNodes(height);

        String underScore = getUnderScores(height);
        String underScoreSpace = multiplyString(" ", underScore.length());

        nodesAtHeight.append(startSpace);
        for (int i = 0; i < noOfNodesAtCurrentHeight; i++) {
            TreeNode node = (TreeNode) queueOfNodes.get(i);
            if (node == null) {
                nodesAtHeight.append(underScoreSpace)
                        .append("  ")
                        .append(underScoreSpace)
                        .append(spaceBetweenTwoNodes);
            } else {
                nodesAtHeight
                        .append(node.left != null ? underScore
                                : underScoreSpace)
                        .append(String.format("%2d", node.value))
                        .append(node.right != null ? underScore
                                : underScoreSpace)
                        .append(spaceBetweenTwoNodes);
            }
        }

        System.out.println(nodesAtHeight.toString().replaceFirst("\\s+$", ""));
    }

    public static String getSpaceBetweenLeftRightBranch(int height) {
        int noOfNodesBetweenLeftRightBranch = ((int) Math.pow(2, height - 1) - 1);

        return multiplyString("  ", noOfNodesBetweenLeftRightBranch);
    }

    public static String getSpaceBetweenRightLeftBranch(int height) {
        int noOfNodesBetweenLeftRightBranch = (int) Math.pow(2, height - 1);

        return multiplyString("  ", noOfNodesBetweenLeftRightBranch);
    }

    public static void printBranches(List<TreeNode> queueOfNodes,
            int noOfNodesAtCurrentHeight, int height) {
        if (height <= 1)
            return;
        StringBuilder brachesAtHeight = new StringBuilder();

        String startSpace = getStartingSpace(height);
        String leftRightSpace = getSpaceBetweenLeftRightBranch(height);
        String rightLeftSpace = getSpaceBetweenRightLeftBranch(height);

        brachesAtHeight
                .append(startSpace.substring(0, startSpace.length() - 1));

        for (int i = 0; i < noOfNodesAtCurrentHeight; i++) {
            TreeNode node = queueOfNodes.get(i);
            if (node == null) {
                brachesAtHeight.append(" ")
                        .append(leftRightSpace)
                        .append(" ")
                        .append(rightLeftSpace);
            } else {
                brachesAtHeight.append(node.left != null ? "/" : " ")
                        .append(leftRightSpace)
                        .append(node.right != null ? "\\" : " ")
                        .append(rightLeftSpace);
            }
        }

        System.out
                .println(brachesAtHeight.toString().replaceFirst("\\s+$", ""));
    }

    public static void prettyPrintTree(TreeNode root) {
        LinkedList<TreeNode> queueOfNodes = new LinkedList<>();
        int height = getMaximumHeight(root);
        int level = 0;
        int noOfNodesAtCurrentHeight = 0;

        queueOfNodes.add(root);

        while (!queueOfNodes.isEmpty() && level < height) {
            noOfNodesAtCurrentHeight = ((int) Math.pow(2, level));

            printNodes(queueOfNodes, noOfNodesAtCurrentHeight, height - level);
            printBranches(queueOfNodes, noOfNodesAtCurrentHeight, height
                    - level);

            for (int i = 0; i < noOfNodesAtCurrentHeight; i++) {
                TreeNode currNode = queueOfNodes.peek();
                queueOfNodes.remove();
                if (currNode != null) {
                    queueOfNodes.add(currNode.left);
                    queueOfNodes.add(currNode.right);
                } else {
                    queueOfNodes.add(null);
                    queueOfNodes.add(null);
                }
            }
            level++;
        }
    }

    public static void main(String[] args) {
        PrettyPrintTree lcs = new PrettyPrintTree(Arrays.asList(80, 30, 90, 20,
                100, 99, 40, 10, 25, 35, 50, 5, 15, 23, 28, 33, 38, 41, 55));
        PrettyPrintTree.prettyPrintTree(lcs.root);
    }
}

Answer 1

nodesAtHeight.toString().replaceFirst("\\s+$", "")

This will recompile a regex each time it is called.

Instead you can create a constant to hold the pattern:

private static final Pattern END_OF_LINE_WHITESPACE = Pattern.compile("\s+$");

and then use it with

END_OF_LINE_WHITESPACE.matcher(nodesAtHeight.toString()).replaceFirst("")

However just finding how many whitespaces are at the end of a string is easy enough to allow for a utility method of the form.

public static String trimEnd(String in){
    for(int i = in.length(); i > 0;i--){
        if(!Character.isWhitespace(in.charAt(i-1))){
            return in.subString(0, i);
        }
    }
    return "";
}

Answer 2

I think your code is modular but I think it is good idea to put the static functions in a separate file named Utility or something. This way you separate Tree data structure and the utility methods so they can be easily reused.

public class PrettyPrintTree {  
    public final TreeNode root;

    public PrettyPrintTree(List<Integer> list) {
        root = PrettyPrintTreeUtil.createTree(list);
    }

}

class TreeNode {
    TreeNode left;
    TreeNode right;
    int value;

    public TreeNode(int value) {
        this.value = value;
    }
}

class PrettyPrintTreeUtil{  
    //all the static utility methods...
}