2
\$\begingroup\$

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);
    }
}
\$\endgroup\$
7
  • \$\begingroup\$ nodesAtHeight.toString().replaceFirst("\\s+$", "") - never do this, EVER. String.replaceX() compiles a regular expression on each call. What you want here is trim ending whitespace - look up Guava's Strings of Apache Commons' StringUtils for such utility methods. \$\endgroup\$
    – user47093
    Jan 21, 2015 at 10:26
  • \$\begingroup\$ @user47093 or just String.trim() (if leading whitespace should also be trimmed) \$\endgroup\$ Jan 21, 2015 at 10:33
  • \$\begingroup\$ @user47093 I didn't want to use an external library for this. Could you tell me what should I use instead of the regex? \$\endgroup\$
    – yadav_vi
    Jan 21, 2015 at 10:37
  • 1
    \$\begingroup\$ Short of an external lib, String.trim() is your best bet. It is orders of magnitude faster than compiling and executing regular expressions. Generally, only use regex where you can't avoid it, try to opimize it (google on optimizing regex - there is a vast discussions about it) and ALWAYS use a precompiled static final Pattern in your code. Of course this stands only for regexes that you'd execute multiple times - initialization doesn't matter. \$\endgroup\$
    – user47093
    Jan 21, 2015 at 10:40
  • 1
    \$\begingroup\$ @yadav_vi a better name for the pattern would be a good idea \$\endgroup\$ Jan 21, 2015 at 11:05

2 Answers 2

2
\$\begingroup\$
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 "";
}
\$\endgroup\$
1
  • \$\begingroup\$ That is how I thought of implementing it (comment above). \$\endgroup\$
    – yadav_vi
    Jan 21, 2015 at 10:54
1
\$\begingroup\$

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...
}
\$\endgroup\$
1
  • \$\begingroup\$ Yes, I thought of making a Utility class where all these methods would be put. Will do that in the next iteration. \$\endgroup\$
    – yadav_vi
    Jan 21, 2015 at 10:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.