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.

Rarely have I read a book whose introductory anecdote so well aligns what the book contains. Moller’s introduction describes the famous mural The School of Athens designed by Raphael in the Vatican. She notes that the popular perception of the Renaissance was that those artists and thinkers like Raphael woke up one fine day, went to a library, re-discovered Classical learning and — violà — The Renaissance. Suddenly science, math, architecture, and governance experience a quantum leap and “civilization,” in a form that the Western modern mind recognizes, returns.

But this is clearly impossible. Knowledge that is not practiced or archived will be lost. It must be curated, maintained, and transmitted.

Asks Moller:

One of his most significant achievements was helping to produce the first English translation of Euclid’s Elements, in 1570. But where had this text been and who had looked after it in the 2,000 years between Euclid writing it in Alexandria [and the 16th century]

They had thrived in the Middle East.

As anyone knows who’s played the empire-building video games like Civilization, first you establish a food supply, then safety as guaranteed by a professional military, and then you get the low-yield/high-payoff leaps forward provided by intellectuals. Because this formula had been lost in religious wars and hamletization in the former territories of the Western Empire, these books found refuge with inky-fingered scholars and magnificence-burnishing enlightened Emirs.

Moller shows that over and over when immigration, tolerance, curiosity, translation and respect thrive under secure conditions, civilization blossoms.

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!