Simple Binary Tree Visualization

mgcadmin 12-10-2021

Visualizing Trees

If you've ever implemented a tree based data structure, chances are when it came time to display the tree, you were left scratching your head. Sure, different tree traversal algorithms allow us to print the contents in different orders, but what about an aesthetically pleasing visualization of the tree structure its self? It turns out that this is an an entire area of study on its own.

A rather in-depth, but somewhat abstract resource on different tree visualization algorithms is this paper brought to us by the Brown University CS department.

If you haven't yet begun delving into graphics libraries, or just want a simple solution for console or other text based tree visualization, the above resource while handy, is way overkill for your needs. What follows is a few SIMPLE algorithms i've encountered while researching the topic myself. Many of these algorithms result from simple modifications to recursive traversal algorithms. Others require a greater deal of manipulation to get the desired output, but one thing is undeniable: efficient tree traversal is center to any tree visualization.

This article assume you are familiar with construction of binary trees. If you need a refresher, i cover their C++ implementation in this article.

Breadth First Search (level-order traversal)

One of the few standard traversal methods that works decently (though the output is rather boring) is a standard level order traversal. Level order traversal of a tree is executed via a queue based Breadth First Search of the entire tree. This will result in each "level" of the tree being printed on its own line, though it lacks any form of symmetry and its immediately apperent which value on the line above is the parent of the current value. That technicality aside, its still a valuable (not to mention essential) algorithm to know.

void BST::levelorderALG1()
{
   int curr_depth = 0;
   std::string spaces;
   std::queue<node*> que;
   if (root != nullptr)
   {
     que.push(root);
   } else {
     cout<<"Tree is empty.\n";
     return;
   }
   while (!que.empty())
   {
     auto curr = que.front();
     que.pop();
     if (curr->d != curr_depth)
     {
       curr_depth = curr->d;
       cout<<endl<<"level "<<curr_depth<<": ";
     }
       cout<<curr->v<<" ";
       if (curr->l != nullptr) que.push(curr->l);
       if (curr->r != nullptr) que.push(curr->r);
     }
}

 

The only part of this algorithm that bears mention is the fact that a data field must be added to the node type to keep track of depth. In a standard Binary Search Tree implementation this is a trivial matter. However, if applied to a self-balancing binary search tree such as a Red-Black tree or AVL tree, extra care must be taken to keep track of changes in node height during rotations.

The output of this algorithm on a randomly generated 25 node BST looks like this:

level 1: 59 
level 2: 36 96 
level 3: 0 48 79 
level 4: 35 47 49 62 91 
level 5: 20 65 81 
level 6: 16 22 69 
level 7: 12 66 72 
level 8: 76 

It's not very visually appealing, but it does give a good basic idea of the structure of the tree, importantly, it organizes the data in a way which can be used as input to a more advanced algorithm.

Preorder Recursive Algorithm 1

The first and simplest algorithm i'm going to illustrate is as the name implies, based on an recursive preorder traversal. I've seen it called the "print spaces"(you'll see why in a second) algorithm in certain spots, though i'm not sure this algorithm has a definitive name at all.

void BST::preorderALG1(node* x, string spaces)
{
  if (x != nullptr)
  {
    cout<<spaces<<x->v<<endl; 
    preorderALG1(x->l, spaces += " ");
    preorderALG1(x->r, spaces += " ");
  }
}

Because of the way the output is formatted by this algorithm, it's really only applicable to smaller data sets. While more visually "interesting" it is still of little practical use.

Unlike the level order traversal, this recursive preorder traversal can be used as-is on both regular AND self balancing binary search trees. It's still not QUITE what were looking for though. lets see if we can do better.

 

Preoder Recursive Algorithm 2

Now that we've established that we can output a tree maintaining parent-child relationships via preorder traversal, how can we improve upon the formatting to give a more concise representation?

This method comes from a post on stack overflow, it gives a horizontal visualization of the tree:

void BST::preorderALG2(std::string prefix, node* x, bool isLeft)
{
  if( x != z )
  {
   std::cout << prefix;
   std::cout << (isLeft ? "├──" : "└──" );
   std::cout << x->v<< std::endl;
   preorderALG2( prefix + (isLeft ? "│ " : " "), x->l, true);
   preorderALG2( prefix + (isLeft ? "│ " : " "), x->r, false);
  }
}

A clever modifcation of the "print spaces" algorithm incorporating unix line drawing characters, it yields a nicer visual:

Much Better! 

---