Displaying Binary Search Trees
Despite the various methods for traversing a tree, displaying the actual structure visually is a more difficult task than one would think. We know that a pre-order traversal gives us some idea of the structure, and Breadth First Traversal gives another view into how the tree is organized.
But converting a list of the nodes contents into a meaning visual representation of the tree remains an elusive task, after reading this article, youll have a better starting point for the visualization of the shape of binary search trees.
Level Order Traversal
The starting point for the method being discussed in this article is the level order traversal of a binary search tree. This is easily accomplished by walking the tree in a breadth first fashion. As previously discussed this is made possible by maintaining a FIFO Queue of nodes. The basic Algorithm for Binary Tree BFS is as follows:
While this traversal method gives the nodes in the order the appear from left to right as we go from the top of the tree towards the bottom, it still doesn’t give us a good idea of the shape. But a very slight modification will give us a better of idea of how the tree is organized.
Level Order Traversal with Level by Level Printing
By keeping track of where each level begins and ends we can print each level of the tree on its own line. This is easily accomplished by using a counter and second loop inside the main loop:
This small change in code gives us a big advantage in visualization when it comes to output.
Small changes, Big Differences
Lets take a look at how this change effects our output. I’m using the above to two algorithms to display the contents of a Red/Black Tree built from the string “ASEARCHINGEXAMPLE” each charachter will be the key of a node. Using our original BFS algorithm, we’re given the following output:
I E R A G N S A C E H M P X A E L
It gives us an idea of the ordering of the nodes, but the not much insight to the structure. Lets take a look at the output of our modified BFS algorithm:
I E R A G N S A C E H M P X A E L
MUCH better, not only do we now know the order of the nodes, but we know how they are distributed amongst the levels of the tree.
From here its not hard to deduce that the tree is laid out like this:
I
/ \
/ \
E R
/ \ / \
A G N S
/ \ / \ \ / \
A C E H MP X
/ \ /
A E L
However, Getting From our modified BFS to the layout above is going to take more than a little work, but its not impossible, So check back for the next article where i will discuss how to produce the kind of output as shown.
