How to Pretty Print a Binary Tree
September 18, 2010 in 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:
. In the future, you should be able to test your algorithms easily!Download Sample Demo Program:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 | // Print the arm branches (eg, / \ ) on a line void printBranches(int branchLen, int nodeSpaceLen, int startLen, int nodesInThisLevel, const deque<BinaryTree*>& nodesQueue, ostream& out) { deque<BinaryTree*>::const_iterator iter = nodesQueue.begin(); for (int i = 0; i < nodesInThisLevel / 2; i++) { out << ((i == 0) ? setw(startLen-1) : setw(nodeSpaceLen-2)) << "" << ((*iter++) ? "/" : " "); out << setw(2*branchLen+2) << "" << ((*iter++) ? "\\" : " "); } out << endl; } // Print the branches and node (eg, ___10___ ) void printNodes(int branchLen, int nodeSpaceLen, int startLen, int nodesInThisLevel, const deque<BinaryTree*>& nodesQueue, ostream& out) { deque<BinaryTree*>::const_iterator iter = nodesQueue.begin(); for (int i = 0; i < nodesInThisLevel; i++, iter++) { out << ((i == 0) ? setw(startLen) : setw(nodeSpaceLen)) << "" << ((*iter && (*iter)->left) ? setfill('_') : setfill(' ')); out << setw(branchLen+2) << ((*iter) ? intToString((*iter)->data) : ""); out << ((*iter && (*iter)->right) ? setfill('_') : setfill(' ')) << setw(branchLen) << "" << setfill(' '); } out << endl; } // Print the leaves only (just for the bottom row) void printLeaves(int indentSpace, int level, int nodesInThisLevel, const deque<BinaryTree*>& nodesQueue, ostream& out) { deque<BinaryTree*>::const_iterator iter = nodesQueue.begin(); for (int i = 0; i < nodesInThisLevel; i++, iter++) { out << ((i == 0) ? setw(indentSpace+2) : setw(2*level+2)) << ((*iter) ? intToString((*iter)->data) : ""); } out << endl; } // 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) void printPretty(BinaryTree *root, int level, int indentSpace, ostream& out) { int h = maxHeight(root); int nodesInThisLevel = 1; int branchLen = 2*((int)pow(2.0,h)-1) - (3-level)*(int)pow(2.0,h-1); // eq of the length of branch for each node of each level int nodeSpaceLen = 2 + (level+1)*(int)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<BinaryTree*> nodesQueue; nodesQueue.push_back(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++) { BinaryTree *currNode = nodesQueue.front(); nodesQueue.pop_front(); if (currNode) { nodesQueue.push_back(currNode->left); nodesQueue.push_back(currNode->right); } else { nodesQueue.push_back(NULL); nodesQueue.push_back(NULL); } } nodesInThisLevel *= 2; } printBranches(branchLen, nodeSpaceLen, startLen, nodesInThisLevel, nodesQueue, out); printLeaves(indentSpace, level, nodesInThisLevel, nodesQueue, out); } |
Anonymous said on December 27, 2010
Can u please post java version?? It would be really helpful..
jerrykickstom said on December 18, 2011
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);
}
}
Catnip said on March 21, 2012
It crashes when it reaches a certain height.
Vincent said on May 28, 2012
You need to set a larger size of your console window
Vincent said on May 28, 2012
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.
ktran said on January 27, 2013
Great! Thanks for great binary tree visualization in console
Sean said on February 5, 2013
Dude. This makes my life infinitely simpler when trying to deal with binary search trees. THANK YOU!