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;
}
}
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")))));
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),
);
}
}
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 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 Knuth2, 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);
}
}
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.
- 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);
}
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.
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.