How to Pretty Print a Binary Tree

Have you ever thought of pretty-printing a binary tree?

Wouldn’t it be cool to output your binary tree like this?

              ______________30______________
             /                              \
      ______20______                  ______40______
     /              \                /              \
  __10__            25__            35            __50
 /      \               \                        /       
 5      15              28                      41

Or, if you prefer, output the tree like this instead? (to save some horizontal space)

        ______30______
       /              \
    __20__          __40__
   /      \        /      \
  10      25      35      50
 /  \       \            /   
 5  15      28          41

I thought it would be really useful to you while you are cracking on binary tree interview questions. Checking if your binary tree is read in correctly into the program takes a lot of effort while you are testing your algorithm.

That’s why I wrote the following C++ code myself. Check out the 60+ lines of code below. Please note that the displayed code below did not include some functions, such as maxHeight() and intToString(). For the full source code which includes a sample driver demo program, please download the source file below.

Implementation:
This implementation is based on my previous post: Printing a Binary Tree in Level Order. I use a deque (double-ended queue) instead of a queue because I want to use std::iterator (in C++, deque supports it but not queue).

For a level, each node is spaced equally with neighboring nodes. This allows a Math equation to be derived easily to calculate the exact location a node will appear in a level.

Last time, when we see an “empty” node, we do not push anything onto the queue. However, this time we need to push two “empty” nodes when we see an “empty” node, since we need to print out the “empty” node as spaces in order to produce a pretty output. Besides, it eases the programming a lot since we do not need to keep track of the number of empty nodes that appear before a valid node.

In the next post, I will talk about the methods I used to read/write a binary tree from/to a file, so that you can run test cases easily.

Huge Update Planned:

I am planning to update all (most, if not all) of my previous posts with sample input/output data sets, as requested by one of my fellow readers, thanks :). In the future, you should be able to test your algorithms easily!

Download Sample Demo Program:

VN:F [1.9.22_1171]
Rating: 4.8/5 (30 votes cast)
How to Pretty Print a Binary Tree, 4.8 out of 5 based on 30 ratings

29 thoughts on “How to Pretty Print a Binary Tree

    1. Richard

      Here is the Java version:


      import java.io.PrintStream;
      import java.util.Deque;
      import java.util.Iterator;
      import java.util.LinkedList;

      public class TreePrinter {
      // Find the maximum height of the binary tree
      private int maxHeight(TreeNode p) {
      if (p == null) return 0;
      int leftHeight = maxHeight(p.left);
      int rightHeight = maxHeight(p.right);
      return (leftHeight > rightHeight) ? leftHeight + 1: rightHeight + 1;
      }

      // Convert an integer value to string
      private String intToString(int val) {
      // ostringstream ss;
      // ss << val;
      // return ss.str();
      return String.valueOf(val);
      }

      // Print the arm branches (eg, / \ ) on a line
      private void printBranches(int branchLen, int nodeSpaceLen, int startLen, int nodesInThisLevel, Deque nodesQueue, PrintStream out) {
      Iterator iter = nodesQueue.iterator();
      for (int i = 0; i < nodesInThisLevel / 2; i++) {

      int w = (i == 0) ? startLen-1 : nodeSpaceLen-2;
      out.print(setw(w, ""));

      TreeNode node = iter.next();
      out.print(node != null ? "/" : " ");

      w = 2*branchLen+2;
      out.print(setw(w, ""));

      node = iter.next();
      out.print(node != null ? "\\" : " ");
      // out << ((i == 0) ? setw(startLen-1) : setw(nodeSpaceLen-2)) << "" << ((*iter++) ? "/" : " ");
      // out << setw(2*branchLen+2) << "" < length) return str;

      String spaces = "";
      int blanks = length - str.length();

      for (int i = 0; i < blanks; i++) {
      spaces += fill;
      }

      spaces += str;
      return spaces;
      }

      @Test
      public void test1() {
      // fill = "*";
      System.out.println(setw(5, "abcde"));
      }

      // Print the branches and node (eg, ___10___ )
      private void printNodes(int branchLen, int nodeSpaceLen, int startLen, int nodesInThisLevel, Deque nodesQueue, PrintStream out) {
      Iterator iter = nodesQueue.iterator();
      for (int i = 0; i < nodesInThisLevel; i++) {
      TreeNode node = iter.next();
      int w = (i == 0) ? startLen : nodeSpaceLen;
      out.print(setw(w, ""));

      fill = (node != null && node.left != null) ? "_" : " ";
      w = branchLen+2;
      out.print(setw(w, node != null ? intToString(node.val) : ""));

      fill = (node != null && node.right != null) ? "_" : " ";
      w = branchLen;
      out.print(setw(w, ""));
      fill = " ";

      // out << ((i == 0) ? setw(startLen) : setw(nodeSpaceLen)) << "" <left) ? setfill('_') : setfill(' '));
      // out << setw(branchLen+2) <data) : "");
      // out <right) ? setfill('_') : setfill(' ')) << setw(branchLen) << "" << setfill(' ');
      }
      // out << endl;
      out.println();
      }

      // Print the leaves only (just for the bottom row)
      private void printLeaves(int indentSpace, int level, int nodesInThisLevel, Deque nodesQueue, PrintStream out) {
      Iterator iter = nodesQueue.iterator();
      for (int i = 0; i < nodesInThisLevel; i++) {
      int w = (i == 0) ? indentSpace+2 : 2*level+2;
      TreeNode node = iter.next();
      out.print(setw(w, node != null ? intToString(node.val) : ""));
      // out << ((i == 0) ? setw(indentSpace+2) : setw(2*level+2)) <data) : "");
      }
      // out << endl;
      out.println();
      }

      // Pretty formatting of a binary tree to the output stream
      // @ param
      // level Control how wide you want the tree to sparse (eg, level 1 has the minimum space between nodes, while level 2 has a larger space between nodes)
      // indentSpace Change this to add some indent space to the left (eg, indentSpace of 0 means the lowest level of the left node will stick to the left margin)
      public void printPretty(TreeNode root, int level, int indentSpace, PrintStream out) {
      int h = maxHeight(root);
      int nodesInThisLevel = 1;

      int branchLen = 2*((int)Math.pow(2.0,h)-1) - (3-level)*(int)Math.pow(2.0,h-1); // eq of the length of branch for each node of each level
      int nodeSpaceLen = 2 + (level+1)*(int)Math.pow(2.0,h); // distance between left neighbor node's right arm and right neighbor node's left arm
      int startLen = branchLen + (3-level) + indentSpace; // starting space to the first node to print of each level (for the left most node of each level only)

      Deque nodesQueue = new LinkedList();
      nodesQueue.offerLast(root);
      for (int r = 1; r < h; r++) {
      printBranches(branchLen, nodeSpaceLen, startLen, nodesInThisLevel, nodesQueue, out);
      branchLen = branchLen/2 - 1;
      nodeSpaceLen = nodeSpaceLen/2 + 1;
      startLen = branchLen + (3-level) + indentSpace;
      printNodes(branchLen, nodeSpaceLen, startLen, nodesInThisLevel, nodesQueue, out);

      for (int i = 0; i < nodesInThisLevel; i++) {
      TreeNode currNode = nodesQueue.getFirst();
      nodesQueue.pollFirst();
      if (currNode != null) {
      nodesQueue.offerLast(currNode.left);
      nodesQueue.offerLast(currNode.right);
      } else {
      nodesQueue.offerLast(null);
      nodesQueue.offerLast(null);
      }
      }
      nodesInThisLevel *= 2;
      }
      printBranches(branchLen, nodeSpaceLen, startLen, nodesInThisLevel, nodesQueue, out);
      printLeaves(indentSpace, level, nodesInThisLevel, nodesQueue, out);
      }

      public static void main(String[] args) {
      TreeNode root = new TreeNode(30);
      root.left = new TreeNode(20);
      root.right = new TreeNode(40);
      root.left.left = new TreeNode(10);
      root.left.right = new TreeNode(25);
      // root.right.left = new TreeNode(35);
      root.right.right = new TreeNode(50);
      root.left.left.left = new TreeNode(5);
      root.left.left.right = new TreeNode(15);
      root.left.right.right = new TreeNode(28);
      root.right.right.left = new TreeNode(41);

      // System.out.println("Tree pretty print with level=1 and indentSpace=0\n\n");
      // Output to console
      new TreePrinter().printPretty(root, 1, 0, System.err);

      // System.out.println("\n\nTree pretty print with level=5 and indentSpace=3,\noutput to file \"tree_pretty.txt\".\n\n");
      // Create a file and output to that file
      // ofstream fout("tree_pretty.txt");
      // Now print a tree that's more spread out to the file
      // printPretty(root, 5, 0, fout);
      }
      }

      VA:F [1.9.22_1171]
      -1
  1. jerrykickstom

    Here is a easier version of printing a binary tree, though in a rotated fashion i.e
    left-right maps to bottom-up:-

    start the call to displayTree with level = 0, lik displayTree(root,0);

    void displayTree(NODE* root,int level){
    int i;
    if(root!=NULL){
    displayTree(root->right, level+1);
    printf(“\n”);
    for(i=0;idata);
    displayTree(root->left, level+1);
    }
    }

    VN:F [1.9.22_1171]
    -2
    1. matheus

      void displayTree(NODE* root,int level){
      int i;
      if(root!=NULL){
      displayTree(root->right, level+1);
      printf(“\n”);
      for(i=0;idata); //What is in this for(??) ?
      displayTree(root->left, level+1);
      }
      }

      VA:F [1.9.22_1171]
      +1
  2. Vincent

    Great!!!!! thank you very much to 1337c0d3r, you save me a lot of time.
    It work really great with some adjust to my purpose and the behavior I need.

    VA:F [1.9.22_1171]
    0
  3. Ven

    Here’s the Python code for pretty printing:

    VA:F [1.9.22_1171]
    +2
    1. Ven

      VA:F [1.9.22_1171]
      +3
  4. Ven

    Half of my code above disappeared despite trying to post it twice. I can’t even edit my post. Reposting the pretty_print method again here.

    VA:F [1.9.22_1171]
    +1
  5. Anupam Srivastava

    This will not print the slashes and underscore, but will print BST in a normal form.

    Output:

    VA:F [1.9.22_1171]
    +6
  6. Pingback: LeetCode | Technical interview solutions

  7. Pingback: PrettyPrint a Binary Tree | DL-UAT

  8. Shahan Khan

    |68| error: ‘pow’ was not declared in this scope|

    68 number line say ‘pow’ was not declared. I can’t fix it. Help me..
    # I run this code on “Code Blocks”.

    VA:F [1.9.22_1171]
    0
  9. Kevin

    I tried inputting large numbers, and it started messing up. I think you need to take into account the integers length when using set width right?

    Could you tell me how I would solve this when working with large numbers?

    VA:F [1.9.22_1171]
    0
  10. Mateo

    Made a JavaScript version of the code, writes the tree to an element with id “displayTree” and uses jQuery.

    Calling drawATree() outputs:

    VA:F [1.9.22_1171]
    0
    1. Mateo

      Final version (the other one didn’t work well with some trees):

      Note that if the numbers grow in size you have to call the printPretty function with a higher “level” parameter.

      VA:F [1.9.22_1171]
      +1
  11. Pingback: python实现二叉树的前、中、后序遍历及按层遍历 - IT大道

  12. Richard

    When the number is single digital, there ___ on the left is more than ___ on the right.

    Like this:

    VA:F [1.9.22_1171]
    0

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use the <code> tag to embed your code.

*