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:

Answer 1

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;
        }
    }
}

Answer 2

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