**1.** `INFO(T)`

= *A*, `INFO(RLINK(T))`

= *C*, etc.; the answer is *H*.

**2.** Preorder: 1245367; symmetric order: 4251637; postorder: 4526731.

**3.** The statement is true; notice, for example, that nodes 4, 5, 6, 7 always appear in this order in exercise 2. The result is immediately proved by induction on the size of the binary tree.

**4.** It is the reverse of postorder. (This is easily proved by induction.)

**5.** In the tree of exercise 2, for example, preorder is 1, 10, 100, 101, 11, 110, 111, using binary notation (which is in this case equivalent to the Dewey system). The strings of digits have been sorted, like words in a dictionary.

In general, the nodes will be listed in preorder if they are sorted lexicographically from left to right, with “blank” ...

Start Free Trial

No credit card required