Coding a basic pretty printer for trees in Java

Question

I need help in understanding how to code a pretty printer for any given binary tree.

I know the first step is to do preorder to get all of the nodes.

I know that during the preorder traversal, that's where all of the prettyness will be implemented.

Just not sure how to get started. I am given a preorder traversal function that works but i'm not sure where to start modifying it or if I should just make my own function.

No code, just asking for ideas on how others would go about it.

And maybe later code if I get desperate :P

To be specific, It should look like this:

Solution 1

If you know the depth of the tree, i.e. the number of levels you can calculate the maximum number of nodes in the last level (which is n² for n=number of levels - 1, 1 element if you have the root only). If you further know the width of the elements (e.g. if you have at most 2-digit numbers each element would have width 2) you can calculate the width of the last level: ((number of elements - 1) * (element width + spacing) + element width).

Actually the above paragraph doesn't matter. All you need is the depth of the tree, i.e. the maximum level that is to be displayed. However, if the tree is sparse, i.e. not all elements of the last level and maybe above are present, you'll need to get the position of the node you're rendering in order to adapt the indent/spacing for that case accordingly.

In your pre-order iteration you can then calculate the indentation and spacing between the elements at each level. The formula for the indent would be: 2^{(max level - level)} - 1 and for the spacing: 2^{(max level - level + 1)} - 1 (level is 1-based)

Example:

       1
   2       3
 4   5   6   7
8 9 A B C D E F

In that tree, the number of levels is 4. The spacing at the last level is 1 whereas the indent is 0. You'll get the following values:

• level 1:
  • indent = 7: (2^(4-1) - 1 = 2³ - 1 = 8 - 1 = 7)
  • first level, so spacing doesn't matter
• level 2:
  • indent = 3: (2^(4-2) - 1 = 2² - 1 = 4 - 1 = 3)
  • spacing = 7 (2^(4-1) - 1 = 2³ - 1 = 8 - 1 = 7)
• level 3:
  • indent = 1: (2^(4-3) - 1 = 2¹ - 1 = 2 - 1 = 1)
  • spacing = 3 (2^(4-2) - 1 = 2² - 1 = 4 - 1 = 3)
• level 4:
  • indent = 0: (2^(4-4) - 1 = 2⁰ - 1 = 1 - 1 = 0)
  • spacing = 1: (2^(4-3) - 1 = 2¹ - 1 = 2 - 1 = 1)

Note that at the last level you'll always have spacing 1 * element width. Thus for a maximum element width of 3 (e.g. 3-digit numbers) you'd have a spacing of 3 at the last level, in order to get some pretty alignment of the upper levels.

Edit: For your pretty print, you'd just have to calculate the indent as width element * level where level would be zero-based. Then if the node is not a leaf, draw it with a opening paranthesis in front and a closing paranthesis after drawing the children, if it is a leaf just draw it and if the leaf is missing, draw double paranthis.

Thus you'd get something like this:

public void printSubtree( int indent, node ) {
  for( int i = 0; i < indent; ++i) {
    System.out.print(" ");
  }

  if( inner node) {
    System.out.println("(" + value);     
    printSubtree(indent + elem width, left child); //this is a recursive call, alternatively use the indent formula above if you don't use recursion
    printSubtree(indent + elem width, right child);

    //we have a new line so print the indent again
    for( int i = 0; i < indent; ++i) {
      System.out.print(" ");
    }
    System.out.println(")"); 
  } else if( not empty) {
    System.out.println(value);
  } else { //empty/non existing node
    System.out.println("()");
  }
}

Solution 2

This works for all inputs and prints a line to link as seen in below figure

package com.sai.samples;

/**
 * @author Saiteja Tokala
 */
import java.util.ArrayList;
import java.util.List;


/**
 * Binary tree printer
 *
 * @author saiteja
 */
public class TreePrinter
{
    /** Node that can be printed */
    public interface PrintableNode
    {
        /** Get left child */
        PrintableNode getLeft();


        /** Get right child */
        PrintableNode getRight();


        /** Get text to be printed */
        String getText();
    }


    /**
     * Print a tree
     *
     * @param root
     *            tree root node
     */
    public static void print(PrintableNode root)
    {
        List<List<String>> lines = new ArrayList<List<String>>();

        List<PrintableNode> level = new ArrayList<PrintableNode>();
        List<PrintableNode> next = new ArrayList<PrintableNode>();

        level.add(root);
        int nn = 1;

        int widest = 0;

        while (nn != 0) {
            List<String> line = new ArrayList<String>();

            nn = 0;

            for (PrintableNode n : level) {
                if (n == null) {
                    line.add(null);

                    next.add(null);
                    next.add(null);
                } else {
                    String aa = n.getText();
                    line.add(aa);
                    if (aa.length() > widest) widest = aa.length();

                    next.add(n.getLeft());
                    next.add(n.getRight());

                    if (n.getLeft() != null) nn++;
                    if (n.getRight() != null) nn++;
                }
            }

            if (widest % 2 == 1) widest++;

            lines.add(line);

            List<PrintableNode> tmp = level;
            level = next;
            next = tmp;
            next.clear();
        }

        int perpiece = lines.get(lines.size() - 1).size() * (widest + 4);
        for (int i = 0; i < lines.size(); i++) {
            List<String> line = lines.get(i);
            int hpw = (int) Math.floor(perpiece / 2f) - 1;

            if (i > 0) {
                for (int j = 0; j < line.size(); j++) {

                    // split node
                    char c = ' ';
                    if (j % 2 == 1) {
                        if (line.get(j - 1) != null) {
                            c = (line.get(j) != null) ? '┴' : '┘';
                        } else {
                            if (j < line.size() && line.get(j) != null) c = '└';
                        }
                    }
                    System.out.print(c);

                    // lines and spaces
                    if (line.get(j) == null) {
                        for (int k = 0; k < perpiece - 1; k++) {
                            System.out.print(" ");
                        }
                    } else {

                        for (int k = 0; k < hpw; k++) {
                            System.out.print(j % 2 == 0 ? " " : "─");
                        }
                        System.out.print(j % 2 == 0 ? "┌" : "┐");
                        for (int k = 0; k < hpw; k++) {
                            System.out.print(j % 2 == 0 ? "─" : " ");
                        }
                    }
                }
                System.out.println();
            }

            // print line of numbers
            for (int j = 0; j < line.size(); j++) {

                String f = line.get(j);
                if (f == null) f = "";
                int gap1 = (int) Math.ceil(perpiece / 2f - f.length() / 2f);
                int gap2 = (int) Math.floor(perpiece / 2f - f.length() / 2f);

                // a number
                for (int k = 0; k < gap1; k++) {
                    System.out.print(" ");
                }
                System.out.print(f);
                for (int k = 0; k < gap2; k++) {
                    System.out.print(" ");
                }
            }
            System.out.println();

            perpiece /= 2;
        }
    }
}

Solution 3

Since the traversal function is recursive, you can pass formatting arguments (such as the number of spaces to indent each node) on to the recursive calls. E.g. if you want to indent 2 spaces for each level in the tree, you can start the recursion with an argument of 0, and then add 2 in each recursive step.

Solution 4

Assume that your Binary tree is represented in the following manner:

public class BinaryTreeModel {

    private Object value;
    private BinaryTreeModel left;
    private BinaryTreeModel right;

    public BinaryTreeModel(Object value) {
        this.value = value;
    }

    // standard getters and setters

}

Then the code for the pretty print the tree could be written like this:

For root node:

public String traversePreOrder(BinaryTreeModel root) {

    if (root == null) {
        return "";
    }

    StringBuilder sb = new StringBuilder();
    sb.append(root.getValue());

    String pointerRight = "└──";
    String pointerLeft = (root.getRight() != null) ? "├──" : "└──";

    traverseNodes(sb, "", pointerLeft, root.getLeft(), root.getRight() != null);
    traverseNodes(sb, "", pointerRight, root.getRight(), false);

    return sb.toString();
}

for child nodes:

public void traverseNodes(StringBuilder sb, String padding, String pointer, BinaryTreeModel node, 
  boolean hasRightSibling) {
    if (node != null) {
        sb.append("\n");
        sb.append(padding);
        sb.append(pointer);
        sb.append(node.getValue());

        StringBuilder paddingBuilder = new StringBuilder(padding);
        if (hasRightSibling) {
            paddingBuilder.append("│  ");
        } else {
            paddingBuilder.append("   ");
        }

        String paddingForBoth = paddingBuilder.toString();
        String pointerRight = "└──";
        String pointerLeft = (node.getRight() != null) ? "├──" : "└──";

        traverseNodes(sb, paddingForBoth, pointerLeft, node.getLeft(), node.getRight() != null);
        traverseNodes(sb, paddingForBoth, pointerRight, node.getRight(), false);
    }
}

Then all you need to do is call the function for the root node like this:

System.out.println(traversePreOrder(root));

This article explains in detail the whole approach - https://www.baeldung.com/java-print-binary-tree-diagram. This idea could be extended to pretty print generic trees, tries and much more.

How to do the same for trie?

Assume the helper classes for the trie are Trie and TrieNode defined as follows:

public class TrieNode{
    public HashMap<Character, TrieNode> children;
    public boolean isWord;
    public TrieNode() {
        children = new HashMap<>();
        isWord = false;
    }
}

and

public class Trie{
    public TrieNode root;
    public Trie() {
        root = new TrieNode();
    }
    // Insert method for trie, search method for trie, delete method for trie not shown as they are not relevant
}

Now, to implement pretty print methods, just insert the two methods in the Trie class:

public String traversePreOrder() {
        if (root == null) {
            return "";
        }

        StringBuilder sb = new StringBuilder();
        sb.append("○");

        Set<Character> childNodeChars = root.children.keySet();
        Iterator<Character> iterator = childNodeChars.iterator();
        while (iterator.hasNext()) {
            Character childC = iterator.next();
            if (!iterator.hasNext())
                traverseNodes(sb, "", "└──", root, childC, false);
            else
                traverseNodes(sb, "", "├──", root, childC, true);
        }

        return sb.toString();
    }

    private void traverseNodes(StringBuilder sb, String padding, String pointer, TrieNode node, Character c, boolean hasNextSibling) {
        sb.append("\n");
        sb.append(padding);
        sb.append(pointer);
        sb.append(c);
        sb.append(node.children.get(c).isWord?"(1)":"");

        StringBuilder paddingBuilder = new StringBuilder(padding);
        paddingBuilder.append(hasNextSibling?"│  ":"   ");

        String paddingForBoth = paddingBuilder.toString();

        TrieNode childNode = node.children.get(c);
        if(childNode == null)
            return;

        Set<Character> childNodeChars = childNode.children.keySet();
        Iterator<Character> iterator = childNodeChars.iterator();
        while (iterator.hasNext()) {
            Character childC = iterator.next();
            if (!iterator.hasNext())
                traverseNodes(sb, paddingForBoth, "└──", childNode, childC, false);
            else
                traverseNodes(sb, paddingForBoth, "├──", childNode, childC, true);
        }
    }

View more solutions

Comments

[The Nail]

Print all items of the same depth, then a newline, and then the items of the next depth. Still to solve: the horizontal position

[The Nail]

Spoiler: stackoverflow.com/questions/4965335/…

[neojb1989]

Also good. A little harder to wrap my head around but I think you may have the best solution. Could you reword it a little more... simply :P

[neojb1989]

Ooh your doing that type of pretty print. sorry I should have specified. I meant something along the lines of: (a (b d e ) (c () (f (g () h ) () ) ) ) for a tree with its preorder traversal being : a b d e c f g h And the tree looks like: a b c d e f g h

[neojb1989]

Wow that did not format at all. Gimmie a sec to put up a picture.

[neojb1989]

Thank you for helping me, could you take a look at the picture I posted and give it one last go. I very much appreciate it.

[Thomas]

@neojb1989 did you see my edit? It should produce what you're askin for (although I left some code for you do to, it's an outline after all).

[neojb1989]

Thank you very much, i think i'll be able to do it now. Appreciate it tons.

[Clint Eastwood]

this is gold! I am not using this for any real (i.e. prod) use case so I don't care if it's fast or not... it just looks awesome! thanks a lot!