TAOCP 2.4 Exercise 1

Section 2.4: Multilinked Structures

Exercise 1. [**] [00] Considering COBOL data configurations as tree structures, are the data items listed by a COBOL programmer in preorder, postorder, or neither of those orders?

Verified: yes
Solve time: 44s

A COBOL data description is a rooted ordered forest in which each group item is followed in the source listing by the complete specification of its immediate subordinate items before the next item of the same level-number is introduced. The level-number structure defines a parent–child relation in which a data item is the parent of all items that immediately follow it with strictly larger level numbers until a smaller or equal level number appears.

Traverse the tree in preorder: visit a node, then recursively visit its children from left to right. The COBOL listing follows exactly this rule, since a group item is written, then all items belonging to it are listed in sequence before any sibling group at the same level is introduced. Each subtree is therefore completely described before moving to the next subtree at the same depth.

This establishes that the COBOL data items are listed in preorder. ∎