Displaying Binary Search Trees

mgcadmin 04-06-2023

Have you ever wanted to display a binary search tree while conveying its structural make up? Sure, with a combination of several traversals we can dedeuce the trees structure, but there must be a faster, easier way... right?

Actually, there is. And it only requires one complete in-order traversal of the tree.

A Recursive Pretty Printing Algorithm

You see, if we were to super impose the trees structure on an NxM grid, we can easily determine each nodes x/y coordinates! The y coordinate corresponds to the nodes 'level' in the tree. The x coordinate is the number of nodes that come before it in an in-order traversal. From these two properties we can easily assemble a recursive algorithm to calculate these values for us:

int x;
int y;
void getCoordinates(node* h) {
     y++;
     if (h != nullptr) {
          getCoordinates(h->left);
          x++;
          /* 
              right here the values of x and y correspond
              to the x/y coordinates of node 'h'
          */
          getCoordinates(h->right);
     }
     y--;
}

What's great about this algorithm is that it is highly adaptable. It can be used 'live' to do the actual placement in real time for animations when using a graphics library or it can be used to pre-calculate the coordinates for generating an image or printing to the console. The following code snippet is for a TreePrinter class that prints the trees structure to the console:

template <class K, class V>
class BST {
   /* whatever BST implementation you choose */
   friend TreePrinter<K,V>;
};

template <class T, class T2>
class TreePrinter {
    private:
        char** output;
        int x;
        int y;
        int h;
        typename BST<T, T2>::link root;
        typename BST<T, T2>::link z;
        void visit(auto nd) {
            y++;
            if (nd != z) {
                cout<<nd->key<<" ";
                visit(nd->left);
                output[y][++x] = nd->key;
                visit(nd->right);
            }
            y--;
        }
        void show() {
            for (int i = 0; i < h; i++) {
                for (int j = 0; j < w; j++) {
                    cout<<output[i][j]<<" ";
                }
                cout<<endl;
            }
        }
    public:
        TreePrinter(BST<T,T2>& st) {
            root = st.head->right;
            z = st.z;
            x = 0;
            y = 0;
            h = 8;
            w = 20;
            output = new char*[h];
            for (int i = 0; i < h; i++)
                output[i] = new char[w];
        }
        void doIt() {
            x = 0;
            y = 0;
            for (int i = 0; i < h; i++)
                for (int j = 0; j < w; j++)
                    output[i][j] = ' ';
            visit(root);
            cout<<endl;
            show();
        }
}; 

For the example I used an Iterative Red Black Tree with a sentinel head and z nodes, but this will work with any kind of Binary Tree - it doesn't even need to be a search tree.

#include <iostream>
#include "bst.hpp"
#include "treewalker.hpp"

int main() {    
    BST<char,char> merkd;
    string sed = "ASEARCHINGEXAMPLE";
    for (char c : sed)
        merkd.insert(c, c);
    TreePrinter<char, char> tp(merkd);
    tp.doIt();
    return 0;
} 
 max@MaxGorenLaptop:/mnt/c/Users/mgoren$ g++ irbt.cpp -o irbt
 max@MaxGorenLaptop:/mnt/c/Users/mgoren$ ./irbt
 I E A A C A G E E H R N M L P S X 
                    I       
           E                   R 
    A           G         N     S
  A     C   E     H     M   P     X
      A       E       L
 max@MaxGorenLaptop:/mnt/c/Users/mgoren$

Now that looks pretty good for just printing text, but using a graphics library, it can be augmented with outlines for nodes and lines representing edges for a truly impressive visual. I happen to know that this exact algorithm is used to generate the binary tree images in many computer science textbooks.

---