Software developer blog

How to generate a random binary tree and visualize it with Graphviz

Yesterday I was testing a small piece of code, that was capable of finding the nth item in the in-order traversal of a binary tree. It was a template function with the root node and n as arguments, and only required that the children nodes should be pointed by public members "left" and "right", while unused children pointers are NULL. (Pretty much the old school way of doing it.)

Of course I didn't want to manually generate test cases. Instead I wrote a little function that can generate a large tree on demand, and used that. Since the boost random library uses a constant seed by default I can rely on the tree to be the same each time the test is ran.

The generator function will expect an array of nodes, begin and end values like this:

Node nodes[SIZE];
Node* root = generateRandomTree(nodes, 0, SIZE);

Where the Node in this case is a simple struct:

struct Node 
    int value;
    Node* left;
    Node* right;

I will expect the nodes in the array to be ordered by the keys. That way generateRandomTree can be a recursive function that will randomly choose a root node, and recursively builds up the left and right sub trees. Here is how it's done:

boost::mt19937 gen; 
Node* generateRandomTree(Node* nodes, int begin, int end) 
    if(begin == end) return NULL;
    boost::uniform_int<> dist(begin, end-1);
    int splitPoint = dist(gen);
    nodes[splitPoint].left = generateRandomTree(nodes, begin, splitPoint);
    nodes[splitPoint].right = generateRandomTree(nodes, splitPoint + 1, end);
    return nodes + splitPoint;

Pretty simple and straightforward.

Now we have a binary tree that could be used for the tests, but it would be nice to make sure that it contains every interesting case. Also in certain cases it might be necessary to know how it looks like, to select test cases from it. So how to quickly visualize it? The easiest way is to use Graphviz.

Here is an example input file for Graphviz:

digraph G{
    node1:left -> node0;
    node7:right -> node8;
    node9:left -> node7;
    node9:right -> node10;
    node6:left -> node5;
    node6:right -> node9;
    node11:left -> node6;
    node12:left -> node11;
    node4:left -> node3;
    node4:right -> node12;
    node14:right -> node15;
    node13:left -> node4;
    node13:right -> node14;
    node2:left -> node1;
    node2:right -> node13;
    node18:left -> node17;
    node18:right -> node19;
    node16:left -> node2;
    node16:right -> node18;

Let's go through that. The first line is required by the dot language used by Graphviz. The second selects the record node type, that is useful when we want to add properties to nodes, and we want the edges to belong to them.

Next we have a block of node definitions. In the label part we print the value and specify the left and right properties. For the exact syntax check the Graphviz documentation. The last part of the file contains the edge definitions. For example "node16:right -> node18;" means, that we want the right pointer of node16 to point to node18.

Once we have the dot file we can just run dot with: "dot -Tjpeg -o smallBinaryTree.jpg". (Another way would be to use the API, and directly generate the image file, but that seemed like an over kill here.) After all that we are rewarded by the image below:

A small binary tree visualized by Graphviz

A small binary tree visualized by Graphviz

P.S.: If the title of this entry was a function name, than it would clearly indicate a violation of the single responsibility principle. And to be honest, probably I should employ SRP on my blog entries as well, since they tend to be quite lengthly 🙂

@ //