Knuth on Trees
Knuth has a charming chapter on Trees in the first book of his famous "The Art of Computer Programming".
I happened to have been bored enough to write some frontend code rendering Trees.
Per Knuth's example:
Yeah, Knuth went hard, didn't he.
This is the code in node form:
[ { "label": "Noah", "children": [ { "label": "Shem", "children": [ { "label": "Aram", "children": [ { "label": "Mash", "children": [] }, { "label": "Gether", "children": [] }, { "label": "Hul", "children": [] }, { "label": "Uz", "children": [] } ] }, { "label": "Lud", "children": [] }, { "label": "Arphaxad", "children": [ { "label": "Salah", "children": [ { "label": "Eber", "children": [ { "label": "Joktan", "children": [] }, { "label": "Peleg", "children": [] } ] } ] } ] }, { "label": "Asshur", "children": [] }, { "label": "Elam", "children": [] } ] }, { "label": "Ham", "children": [ { "label": "Canaan", "children": [ { "label": "Hamathite", "children": [] }, { "label": "Zemarite", "children": [] }, { "label": "Arvadite", "children": [] }, { "label": "Sinite", "children": [] }, { "label": "Arkite", "children": [] }, { "label": "Hivite", "children": [] }, { "label": "Girgasite", "children": [] }, { "label": "Amorite", "children": [] }, { "label": "Jebusite", "children": [] }, { "label": "Heth", "children": [] }, { "label": "Sidon", "children": [] } ] }, { "label": "Phut", "children": [] }, { "label": "Mizraim", "children": [ { "label": "Caphtorim", "children": [] }, { "label": "Calushim", "children": [] }, { "label": "Pathrusim", "children": [] }, { "label": "Napthuhim", "children": [] }, { "label": "Lehabim", "children": [] }, { "label": "Anamim", "children": [] }, { "label": "Ludim", "children": [] } ] }, { "label": "Cush", "children": [ { "label": "Nimrod", "children": [] }, { "label": "Sabtechah", "children": [] }, { "label": "Raamah", "children": [ { "label": "Dedan", "children": [] }, { "label": "Sheba", "children": [] } ] }, { "label": "Havilah", "children": [] }, { "label": "Seba", "children": [] } ] } ] }, { "label": "Japheth", "children": [ { "label": "Tiras", "children": [] }, { "label": "Meshech", "children": [] }, { "label": "Tubal", "children": [] }, { "label": "Javan", "children": [ { "label": "Dodanim", "children": [] }, { "label": "Kittim", "children": [] }, { "label": "Tarshish", "children": [] }, { "label": "Elishah", "children": [] } ] }, { "label": "Madai", "children": [] }, { "label": "Magog", "children": [] }, { "label": "Gomer", "children": [ { "label": "Togarmah", "children": [] }, { "label": "Riphath", "children": [] }, { "label": "Askenaz", "children": [] } ] } ] } ] } ]
Something that bothered me in developing these trees is how repetitive and "wide" they can be.
Basically, the most elegant form of the tree, is the tree itself. The boilerplate, in contrast, is very messy.
Is there a way to remedy this? Fortunately, Knuth had some handy answers.
He shows a few representations of a tree, most of which I'll show (the nested sets representation doesn't lend well to text format).
The first up is an indent-based tree. Basically, the indentation level is the depth of the branch. One weakness is that these have to be in sequential order. (The below uses 4 spaces for indentation.)
The second is a list-based system, using the list number to determine placement on the tree. What's interesting about this is that this allows the client to define the nodes out-of-order.
The last is a parenthesis-based system. The first string within a parenthesis is the node name, and what remains are child definitions. This one personally gets hard to read.
Ultimately, what struck me as the most elegant and easiest form to write was the list representation. It's just easy to keep track of.
And so, this is the opening example in list representation form:
1 Noah 1.1 Shem 1.1.1 Aram 1.1.1.1 Mash 1.1.1.2 Gether 1.1.1.3 Hul 1.1.1.4 Uz 1.1.2 Lud 1.1.3 Arphaxad 1.1.3.1 Salah 1.1.3.1.1 Eber 1.1.3.1.1.1 Joktan 1.1.3.1.1.2 Peleg 1.1.4 Asshur 1.1.5 Elam 1.2 Ham 1.2.1 Canaan 1.2.1.1 Hamathite 1.2.1.2 Zemarite 1.2.1.3 Arvadite 1.2.1.4 Sinite 1.2.1.5 Arkite 1.2.1.6 Hivite 1.2.1.7 Girgasite 1.2.1.8 Amorite 1.2.1.9 Jebusite 1.2.1.10 Heth 1.2.1.11 Sidon 1.2.2 Phut 1.2.3 Mizraim 1.2.3.1 Caphtorim 1.2.3.2 Calushim 1.2.3.3 Pathrusim 1.2.3.4 Napthuhim 1.2.3.5 Lehabim 1.2.3.6 Anamim 1.2.3.7 Ludim 1.2.4 Cush 1.2.4.1 Nimrod 1.2.4.2 Sabtechah 1.2.4.3 Raamah 1.2.4.3.1 Dedan 1.2.4.3.2 Sheba 1.2.4.4 Havilah 1.2.4.5 Seba 1.3 Japheth 1.3.1 Tiras 1.3.2 Meshech 1.3.3 Tubal 1.3.4 Javan 1.3.4.1 Dodanim 1.3.4.2 Kittim 1.3.4.3 Tarshish 1.3.4.4 Elishah 1.3.5 Madai 1.3.6 Magog 1.3.7 Gomer 1.3.7.1 Togarmah 1.3.7.2 Riphath 1.3.7.3 Askenaz
These are quite wide and cumbersome in themselves. One can easily see how difficult it is for a writer to remember each bullet.
Binary Trees and Traversal
Knuth has an eye-popping algorithm for converting n-ary trees to binary trees. B(F) is the function transforming the n-ary tree to the binary tree. I quote this directly from my edition:
- If n = 0, B(F) is empty.
- If n > 0, the root of B(F) is root(T1); the left subtree of B(F) is B(T11, T12, ..., T1m), where T11, T12, ..., T1m are the subtrees of root(T1); and the right subtree of B(F) is B(T2, ..., Tn).
We can combine this with Knuth's categories of binary tree traversal: pre-order, in-order, post-order. The code is below.
And so, we have the converted family tree of Noah:
let left, right;
if (node.children) {
[left, right] = node.querySelectorAll(`:scope > .children:not(.lines) > .nodeContainer`);
}
yield node.querySelector(':scope > .node');
if (left) {
yield* preOrder(left);
}
if (right) {
yield* preOrder(right);
}
Knuth does mention the traversal order for n-ary trees, but those are more boring because n-ary trees are less structured than binary trees. However, he mentions that n-ary pre-order is dynastic order. So why not check it out? Knuth provides us with the lineage of English monarchs:
1 Charles III 1.1 Elizabeth II 1.1.1 Elizabeth 1.1.1.1 Cecillia 1.1.1.1.1 Caroline 1.1.1.1.1.1 Anne 1.1.1.1.1.2 Edwyn 1.1.1.1.2 Charles 1.1.1.1.2.1 Anne 1.1.1.1.2.2 William 1.1.1.2 Claude 1.1.1.2.1 Frances 1.1.1.2.1.1 Henrietta 1.1.1.2.1.2 Oswald 1.1.1.2.2 Claude 1.1.1.2.2.1 Charlotte 1.1.1.2.2.2 Thomas 1.1.2 George VI 1.1.2.1 Mary 1.1.2.1.1 Mary 1.1.2.1.1.1 Augustua 1.1.2.1.1.2 Adolphus 1.1.2.1.2 Francis 1.1.2.1.2.1 Claudine 1.1.2.1.2.2 Alexander 1.1.2.2 George V 1.1.2.2.1 Alexandra 1.1.2.2.1.1 Louise 1.1.2.2.1.2 Christian IX 1.1.2.2.2 Edward VII 1.1.2.2.2.1 Victoria 1.1.2.2.2.2 Albert 1.2 Philip 1.2.1 Alice 1.2.1.1 Victoria 1.2.1.1.1 Alice 1.2.1.1.1.1 Victoria 1.2.1.1.1.2 Albert 1.2.1.1.2 Louis IV 1.2.1.1.2.1 Elizabeth 1.2.1.1.2.2 Charles 1.2.1.2 Louis 1.2.1.2.1 Julia 1.2.1.2.1.1 Sophie 1.2.1.2.1.2 Maurice 1.2.1.2.2 Alexander 1.2.1.2.2.1 Wilhelmina 1.2.1.2.2.2 Louis II 1.2.2 Andrew 1.2.2.1 Olga 1.2.2.1.1 Alexandra 1.2.2.1.1.1 Louise 1.2.2.1.1.2 Joseph 1.2.2.1.2 Konstantin 1.2.2.1.2.1 Charlotte 1.2.2.1.2.2 Nicholas I 1.2.2.2 George I 1.2.2.2.1 Louise 1.2.2.2.1.1 Charlotte 1.2.2.2.1.2 William 1.2.2.2.2 Christian IX 1.2.2.2.2.1 Louise 1.2.2.2.2.2 William
And so we see in real-time the order of succession of the English royal line.
I actually find Knuth simultaneously both really interesting and really boring. The programming part is surprisingly the most boring part of the book, and though Knuth insists one do the exercise sets, it's not immediately clear what one learns from them. However, the conceptual stuff is extremely interesting. Overall I would love to have all the volumes, but based on Knuth's instructions I don't think I have the mind suitable for his teaching style.
I don't know why I devoted so much time to prepare this page. Hopefully it amuses you as it half-did for me.