5
\$\begingroup\$

I was going through this tutorial for Pretty Printing a binary search tree and decided to implement my own version. Here is my implementation. This version works only for trees that are complete binary tree. I would like to know what all optimisations can be done (errors present can be removed) in the code.

public class PrettyPrintTree {

    private List<Integer> listOfNodes;
    public TreeNode root;

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

    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 getStartingSpace(int height) {
        int noOfSpaces = ((int) Math.pow(2, height - 1)) / 2;

        StringBuilder startSpaceStringBuilder = new StringBuilder();
        for (int i = 0; i < noOfSpaces; i++) {
            // No. of spaces added everytime is the width of every node value
            startSpaceStringBuilder.append("  ");
        }
        return startSpaceStringBuilder.toString();
    }

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

        StringBuilder underScoreStringBuilder = new StringBuilder();
        for (int i = 0; i < noOfUnderScores; i++) {
            // No. of underscores added everytime is the width of every node
            // value
            underScoreStringBuilder.append("__");
        }
        return underScoreStringBuilder.toString();
    }

    private static String getSpaceBetweenTwoNodes(int height) {
        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;

        StringBuilder spaceBetweenNodesStringBuilder = new StringBuilder();
        for (int i = 0; i < noOfSpacesBetweenTwoNodes; i++) {
            spaceBetweenNodesStringBuilder.append("  ");
        }
        return spaceBetweenNodesStringBuilder.toString();
    }

    private static void printNodes(LinkedList<TreeNode> queueOfNodes,
            int noOfNodesAtCurrentHeight, int height) {
        StringBuilder nodesAtHeight = new StringBuilder();
        String startSpace = getStartingSpace(height);
        String spaceBetweenTwoNodes = getSpaceBetweenTwoNodes(height);
        String underScore = getUnderScores(height);

        nodesAtHeight.append(startSpace);

        for (int i = 0; i < noOfNodesAtCurrentHeight; i++) {
            TreeNode node = (TreeNode) queueOfNodes.get(i);
            if (node == null)
                continue;
            queueOfNodes.add(node.left);
            queueOfNodes.add(node.right);
            nodesAtHeight.append(underScore);
            nodesAtHeight.append(String.format("%2d", node.value));
            nodesAtHeight.append(underScore);
            nodesAtHeight.append(spaceBetweenTwoNodes);
        }
        nodesAtHeight.substring(0, nodesAtHeight.length()
                - spaceBetweenTwoNodes.length());

        System.out.println(nodesAtHeight.toString());
    }

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

        StringBuilder spaceBetweenLeftRightStringBuilder = new StringBuilder();
        for (int i = 0; i < noOfNodesBetweenLeftRightBranch; i++) {
            spaceBetweenLeftRightStringBuilder.append("  ");
        }
        return spaceBetweenLeftRightStringBuilder.toString();
    }

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

        StringBuilder spaceBetweenLeftRightStringBuilder = new StringBuilder();
        for (int i = 0; i < noOfNodesBetweenLeftRightBranch; i++) {
            spaceBetweenLeftRightStringBuilder.append("  ");
        }
        return spaceBetweenLeftRightStringBuilder.toString();
    }

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

        String startSpace = getStartingSpace(height);
        // startSpace.substring(0, startSpace.length());
        String leftRightSpace = getSpaceBetweenLeftRightBranch(height);
        String rightLeftSpace = getSpaceBetweenRightLeftBranch(height);

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

        for (int i = 0; i < noOfNodesAtCurrentHeight; i++) {
            brachesAtHeight.append("/").append(leftRightSpace).append("\\")
                    .append(rightLeftSpace);
        }
        brachesAtHeight.substring(0,
                brachesAtHeight.length() - rightLeftSpace.length());

        System.out.println(brachesAtHeight.toString());
    }

    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++)
                queueOfNodes.remove();
            level++;
        }
    }

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

3 Answers 3

4
\$\begingroup\$

The private field listOfNodes can be converted to a local variable, and actually, it can also be inlined in the constructor:

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

Whenever possible, you should declare variable types with interfaces instead of implementation, for example instead of this:

private static void printNodes(LinkedList<TreeNode> queueOfNodes,
                               int noOfNodesAtCurrentHeight, int height) {

It would be better this way:

private static void printNodes(List<TreeNode> queueOfNodes,
                               int noOfNodesAtCurrentHeight, int height) {

In the same method, you have this loop:

    for (int i = 0; i < noOfNodesAtCurrentHeight; i++) {
        TreeNode node = (TreeNode) queueOfNodes.get(i);

The cast to TreeNode is unnecessary, as the type of queueOfNodes is guaranteed by the method signature, so you can simply write as:

TreeNode node = queueOfNodes.get(i);

In the printBranches method, the queueOfNodes parameter is unused, so you should remove it, changing the method signature to this:

private static void printBranches(int noOfNodesAtCurrentHeight, int height) {

You have this code duplicated in two methods:

    StringBuilder spaceBetweenLeftRightStringBuilder = new StringBuilder();
    for (int i = 0; i < noOfNodesBetweenLeftRightBranch; i++) {
        spaceBetweenLeftRightStringBuilder.append("  ");
    }
    return spaceBetweenLeftRightStringBuilder.toString();

It would be better to move this logic to its own method and reuse it.

Actually you have this kind of duplication in multiple other places as well, when building strings. You could reduce duplicated segments more aggressively by creating a parameterized string builder that concatenates a string \$N\$ times (the duplicated operation).

for example:

public 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();
}

In the prettyPrintTree method, the variable initialization int noOfNodesAtCurrentHeight = 0; is unnecessary, as the variable is always reassigned inside the while loop. In fact it would be best to declare the variable inside the loop.


Why the line break in the middle of the statement here:

        printBranches(noOfNodesAtCurrentHeight, height
                - level);

The statement is short enough (69 characters) without the line break:

        printBranches(noOfNodesAtCurrentHeight, height - level);
\$\endgroup\$
4
  • \$\begingroup\$ You could reduce duplicated segments more aggressively by creating a parameterized string builder that concatenates a string N times. I don't know how to do this, could you show an example? \$\endgroup\$
    – yadav_vi
    Jan 21, 2015 at 1:23
  • 1
    \$\begingroup\$ Also, the names have gotten out of hand. I mean it is nice to have meaningful names, but these seem way too long. \$\endgroup\$
    – yadav_vi
    Jan 21, 2015 at 1:26
  • \$\begingroup\$ @yadav_vi see my update, with an example multiplyString implementation that many of your methods could reuse instead of reimplementing the same lines over and over again. \$\endgroup\$
    – janos
    Jan 21, 2015 at 7:43
  • \$\begingroup\$ I thought you were talking about some Design Pattern. I have implemented something of the same sort in my extended implementation, will soon post a follow up question soon. \$\endgroup\$
    – yadav_vi
    Jan 21, 2015 at 7:57
4
\$\begingroup\$

In addition to what janos said, you could make variables final if you know that variables wont change once initialized.

\$\endgroup\$
2
\$\begingroup\$

Some notes:

  1. int noOfNodesInSubTreeOfNode = ((int) Math.pow(2, height - 1)) / 2;
    (in getSpaceBetweenTwoNodes())

    can be easily changed to:

    int noOfNodesInSubTreeOfNode = (int) Math.pow(2, height - 2);

    because: \$\frac{2^x}2= 2^{x-1}\$

    This also applies to getStartingSpace().

  2. return (leftHeight > rightHeight) ? leftHeight + 1 : rightHeight + 1;
    (in getMaximumHeight())

    can be:

    return (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;

    This is a matter of preference. You may think "no", but I think it makes it easier to understand.

  3. for (int i = 0; i < noOfNodesAtCurrentHeight; i++) queueOfNodes.remove();

    Always put braces. If you don't do so, horrible bugs can occur.

\$\endgroup\$
3
  • 1
    \$\begingroup\$ horribly hard to spot bugs... \$\endgroup\$
    – RubberDuck
    Jan 21, 2015 at 0:59
  • \$\begingroup\$ I didn't do int noOfNodesInSubTreeOfNode = (int) Math.pow(2, height - 2); for clearer understanding. \$\endgroup\$
    – yadav_vi
    Jan 21, 2015 at 1:25
  • 1
    \$\begingroup\$ @yadav_vi Then use comments. \$\endgroup\$ Jan 21, 2015 at 4:49

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.