Knuth on the Direction of the Tree in Computer Science

& (verbiage overflow)Mon 07 July 2014RSS

Today I read Danny Cohen’s 1980 paper, “On Holy Wars and a Plea for Peace.” It was recommended in the Rhodes and Goerzen networking book I mentioned in my last post. I am enjoying networking more and more. I already have a lot of experience thinking about encodings, since most of my early involvement with computers dealt with Chinese and was confounded first by conflicting encoding schemes (principally big5 vs. GB, though there were further complications) and then by poor support for Unicode (which Python 3.3 resolved once and for all). I enjoy encodings a lot, and this is more of a related topic, but deeper.

Although it has a serious point, Cohen’s paper is whimsical and says this whimsical thing:

… Anyone who was brought up by computer scientists, rather than by botanists, knows that trees grow downward, having their roots at the top of the page and their leaves down below. Computer scientists seldom remember which way “up” really is.

But then there is a reference to sec. 2.3 of Knuth’s Art of Computer Programming, where Knuth says about tree-direction the same thing that Cohen says about byte-ordering: that it may seem silly but that consistency is important for the field. Knuth continues that while working on the book he drew trees from the bottom up for the first two years (preferring to “adopt nature’s time-honored tradition”), before discovering that 80% of the cases he examined had them the other way. He goes on:

There is an overwhelming tendency to make hand-drawn charts grow downwards instead of upwards (and this is easy to understand in view of the way we write); even the word “subtree,” as opposed to “supertree,” tends to connote a downward relationship.

And he says he is now going to write trees top to bottom, and adds:

Corresponding to this orientation, we should perhaps call the root node the apex of the tree, and speak of nodes at shallow and deep levels. (Third edition, pp. 309–11)

When I feel frustrated at things in the programming world, especially how trendy it has become and how filled with inexact diction and pronunciation, Knuth is a balm, plain and simple.


Comments are enabled.