Drawing Presentable Trees

What are we doing here

We want to figure out how to lay out trees nicely. Let's build some trees, draw them, and start inventing principles until we have nice-looking trees.

TK: put an example of the finished product here

TK: table of contents

We need a tree

A tree has some data, and some children.

class Tree {
  data: string;
  children: Tree[];

  constructor(data: string, ...children: Tree[]) {
    this.data = data;
    this.children = children;
  }
}

listing 1

Let's start by limiting ourselves to binary trees, trees which have no more than 2 children per node.

const tree = new Tree("root",
  new Tree("l"),
  new Tree("r",
    new Tree("r2",
      new Tree("r3",
        new Tree("r4")))));

listing 2

In order to avoid adding drawing state to our nice clean Tree structure, let's create a DrawTree to wrap it and maintain drawing context.

Future functions will have to add more state, but this is what we'll start with.

class DrawTree {
  x: number;
  y: number;
  children: DrawTree[];

  constructor(
    tree: Tree,
    depth: number = 0,
  ) {
    this.x = -1;
    this.y = depth;
    this.children = tree.children.map(
      (t) => new DrawTree(t, this, depth + 1),
    );
  }
}

listing 3

How do we visit each node

To draw our tree, we're going to need to visit each node in the tree and figure out where to place it. Before we do though, we should discuss three ways to visit each node in a binary tree.

In each of the following diagrams, the numbers represent the order in which the nodes was visited.

In an inorder traversal, visit the left child of a node first, then the node itself, then the right child.

figure 1

In a preorder traversal, visit the the node itself first, then its children.

figure 2

In a postorder traversal, visit the the children of the node first, then the node.

figure 3

In the beginning, there was Knuth

The particular type of drawing that we'll be making is one where the root is at the top, its children are below it, and so on. This type of diagram, and thus this entire class of problems, owes largely to Donald Knuth², from whom we will draw our first two principles:

Principle 1: The edges of the tree should not cross each other.

Principle 2: All nodes at the same depth should be drawn on the same horizontal line.

The Knuth algorithm has the advantage of simplicity and speed, but it only works on binary trees and it can produce some misshapen drawings. It is an inorder traversal of a tree, with a global counter that is used as the x variable, then incremented at each node.

let knuth_x = 0;
function KnuthLayout(tree: DrawTree, depth: number = 0) {
  if (tree.children[0]) {
    KnuthLayout(tree.children[0], depth + 1);
  }
  tree.x = knuth_x;
  tree.y = depth;
  knuth_x += 1;
  if (tree.children[1]) {
    KnuthLayout(tree.children[1], depth + 1);
  }
}

listing 4

Here's what the tree we made a minute ago looks like when laid out with this algorithm. Each node gets its own x value, which gives the tree an imbalanced, awkward look.

figure 4

Trying to draw graphs without re-using x positions can make them very wide, and quite wasteful of space. Let's add a new principle to our drawings:

Principle 3: Trees should be drawn as narrowly as possible

From the bottom up

In 1979, 8 years after Knuth published about the tree layout problem, Charles Wetherell and Alfred Shannon published about some of the improvements they'd found.

To generate the minimum-width tree that satisfies the principles laid out so far, they showed that you can:

maintain the a list of the next available slot in each row
assign the current node the next available slot
increment the slot counter

function WSMinwidth(tree: DrawTree) {
  const nexts = new Uint32Array(256);
  function minwidth(tree: DrawTree, depth: number = 0) {
    tree.x = nexts[depth];
    tree.y = depth;
    nexts[depth] += 1;
    tree.children.forEach((t) => minwidth(t, depth + 1));
  }
  minwidth(tree);
}

listing 5

The result is narrow, but not very pleasing.

As it can be quite difficult to determine relationships in this diagram, let's introduce a new principle that should make it easier to see what node is the parent of what children.

figure 5

Principle 4: A parent should be centered over its children

Up to now, we've been able to get away with very simple algorithms to draw trees because we've not really had to consider local context; we've relied on global counters to keep our nodes from overlapping each other. In order to satisfy the principle that a parent should be centered over its children, we'll need to consider each node's local context, and so a few new strategies are necessary.

The first strategy that Wetherell and Shannon introduced is to build trees up from the bottom with a post-order traversal of the tree, instead of going from the top down like listing 4, or through the middle like listing 5. Once you look at the tree this way, centering the parent is an easy operation - divide its children's x coordinates in half.

We must remember, though, to stay mindful of the left side of the tree when constructing the right.

Figure 6 shows a scenario where the right side of the tree has been pushed out to the right in order to accommodate the left. To accomplish this separation, Wetherell and Shannon maintain the array of next available spots introduced with listing 4, but only use the next available spot if centering the parent would cause the right side of the tree to overlap the left side.f got pushed to the right

figure 6