Recently I was practicing building an implementation of a binary search tree (BST), an important data structure often discussed in interviews, in JavaScript. While iterating, I found the ability to draw pretty pictures (“directed graphs”) of the structure helpful. This became even more important when the data collection got big or when the operation got complex e.g. deletion of an interior node with re-homing of “orphans”.

In this post, I’ll show how to get started with visualizing complex structures with directed graphs. At the end of this post, you’ll see how I created a BST from a shuffled Array of Integers and displayed its structure as an image file using Graphviz. While we’ll be working with a BST, this technique is helpful for many data structures, and the odd diagram needed to communicate with your team. Along the way, we’ll see how the approach we’re taking aligns with “The Unix Philosophy.”

With this knowledge, instead of inspecting a BST like this with console.log():

{
  root: Node {
    value: 33,
    left: Node { value: 3, left: null, right: null },
    right: Node { value: 72, left: null, right: null }
  }
}

we can look at:

That seems easier to reason about to me!

In a previous post, I demonstrated how we can create simple text-based files that represent directed graphs and feed them to dot, a program that can create directed graphs as PNG or PDF output. We wanted to add this capability so that the “thinking” of the binary search tree (BST) was visible in a way that helps us learn more about this important data structure.

I’ve cleaned up the ideas in that post and have shared them as a repository. The branch 01-add-graphviz-printer has code and tests (npm test) to do what was described in the previous post. Emit the dot source file by running npm -s run dev (-s prevents NPM output from going into our dot source file and messing it up).

At the end of my previous post, however, I teased that it’d be really great to be able to visualize the logic behind a BST node deletion operation. By extending the code on 01-add-graphviz-printer, I was able to demonstrate what deletion of a BST node looks like.

Here’s a preview:

After the jump I show the code that made this possible.