TAOCP 5.4.4 Exercise 19

Exercise 19. ▶ [22] (R. M. Karp.) Find a binary tree that is not 3-fifo.

Verified: no
Solve time: 1h02m

Solution

The binary tree that is not 3-fifo is the tree depicted in the invalid configurations (4') of the text.
In the read‑forward (FIFO) tree representation, the children of a node are ordered according to the “first formed, first grown on” rule.
The invalid configurations (4') are the two ordered labeled trees in which a node has its two children on tapes (i) and (j) (with (i \ne j)) in the order that contradicts the FIFO discipline.
Consequently, any binary tree that forces such a pattern in every possible 3‑tape labeling is not 3-fifo.

The smallest such tree is the binary tree with 5 leaves shown in (4').
It has the following structure (where internal nodes are merges and leaves are initial runs):

root (R) with left child (e) (a leaf) and right child (N_4);
(N_4) with left child (d) (a leaf) and right child (N_3);
(N_3) with left child (c) (a leaf) and right child (N_2);
(N_2) with left child (a) and right child (b) (both leaves).

The left‑to‑right order of the children is fixed by the tree representation.

Assume this tree admits a 3‑fifo labeling.
Each internal node together with its two children must use three distinct tapes (otherwise two runs would be read from the same tape simultaneously).
Because there are only three tapes, the labels along any path from the root to a leaf must cycle through the three tapes.

Consider the tape that carries the leaf (e) (the left child of the root).
The parent of (e) is (R).
The other child of (R) is (N_4), which lies on a different tape.
The node (N_4) is created at its merge, which occurs after the merges that create its descendants.
In particular, the leaf (d) (left child of (N_4)) is created at time 0, while (N_4) is created later.
Since (e) and (d) are on the same tape (as forced by the distinctness constraints and the cyclic labeling), the FIFO order on that tape requires that the merge consuming (e) (namely (R)) occurs before the merge consuming (d) (namely (N_4)).
But (R) is the parent of (N_4); in any merge sequence (R) must occur after (N_4).
This contradiction shows that no valid labeling exists.

Hence the binary tree described above is not 3-fifo.

∎