Print a binary tree in a pretty way

void btree::postorder(node* p, int indent)
{
    if(p != NULL) {
        if(p->right) {
            postorder(p->right, indent+4);
        }
        if (indent) {
            std::cout << std::setw(indent) << ' ';
        }
        if (p->right) std::cout<<" /\n" << std::setw(indent) << ' ';
        std::cout<< p->key_value << "\n ";
        if(p->left) {
            std::cout << std::setw(indent) << ' ' <<" \\\n";
            postorder(p->left, indent+4);
        }
    }
}

With this tree:

btree *mytree = new btree();
mytree->insert(2);
mytree->insert(1);
mytree->insert(3);
mytree->insert(7);
mytree->insert(10);
mytree->insert(2);
mytree->insert(5);
mytree->insert(8);
mytree->insert(6);
mytree->insert(4);
mytree->postorder(mytree->root);

Would lead to this result:

enter image description here


In order to pretty-print a tree recursively, you need to pass two arguments to your printing function:

  • The tree node to be printed, and
  • The indentation level

For example, you can do this:

void BinarySearchTree::postorder(tree_node* p, int indent=0)
{
    if(p != NULL) {
        if(p->left) postorder(p->left, indent+4);
        if(p->right) postorder(p->right, indent+4);
        if (indent) {
            std::cout << std::setw(indent) << ' ';
        }
        cout<< p->data << "\n ";
    }
}

The initial call should be postorder(root);

If you would like to print the tree with the root at the top, move cout to the top of the if.


It's never going to be pretty enough, unless one does some backtracking to re-calibrate the display output. But one can emit pretty enough binary trees efficiently using heuristics: Given the height of a tree, one can guess what the expected width and setw of nodes at different depths. There are a few pieces needed to do this, so let's start with the higher level functions first to provide context.

The pretty print function:

   // create a pretty vertical tree
   void postorder(Node *p)
   {
      int height = getHeight(p) * 2;
      for (int i = 0 ; i < height; i ++) {
         printRow(p, height, i);
      }
   }

The above code is easy. The main logic is in the printRow function. Let's delve into that.

void printRow(const Node *p, const int height, int depth)
{
        vector<int> vec;
        getLine(p, depth, vec);
        cout << setw((height - depth)*2); // scale setw with depth
        bool toggle = true; // start with left
        if (vec.size() > 1) {
                for (int v : vec) {
                        if (v != placeholder) {
                                if (toggle)
                                        cout << "/" << "   ";
                                else
                                        cout << "\\" << "   ";
                        }
                        toggle = !toggle;
                }
                cout << endl;
                cout << setw((height - depth)*2);
        }
        for (int v : vec) {
                if (v != placeholder)
                        cout << v << "   ";
        }
        cout << endl;
}

getLine() does what you'd expect: it stores all nodes with a given equal depth into vec. Here's the code for that:

void getLine(const Node *root, int depth, vector<int>& vals)
{
        if (depth <= 0 && root != nullptr) {
                vals.push_back(root->val);
                return;
        }
        if (root->left != nullptr)
                getLine(root->left, depth-1, vals);
        else if (depth-1 <= 0)
                vals.push_back(placeholder);
        if (root->right != nullptr)
                getLine(root->right, depth-1, vals);
        else if (depth-1 <= 0)
                vals.push_back(placeholder);
}

Now back to printRow(). For each line, we set the stream width based on how deep we are in the binary tree. This formatting will be nice because, typically, the deeper you go, the more width is needed. I say typically because in degenerate trees, this wouldn't look as pretty. As long as the tree is roughly balanced and smallish (< 20 items), it should turn out fine. A placeholder is needed to align the '/' and '\' characters properly. So when a row is obtained via getLine(), we insert the placeholder if there isn't any node present at the specified depth. The placeholder can be set to anything like (1<<31) for example. Obviously, this isn't robust because the placeholder could be a valid node value. If a coder's got spunk and is only dealing with decimals, one could modify the code to emit decimal-converted strings via getLine() and use a placeholder like "_". (Unfortunately, I'm not such a coder :P)

The result for the following items inserted in order: 8, 12, 4, 2, 5, 15 is

       8   
     /   \   
     4   12   
   /   \   \   
   2   5   15

getHeight() is left to the reader as an exercise. :) One could even get prettier results by retroactively updating the setw of shallow nodes based on the number of items in deeper nodes. That too is left to the reader as an exercise.

Tags:

C++

Recent Posts