Mathematics for Computer Science

6.5. Induction in Computer Science 191

Thesize,jGj, ofG 2 binary-2PTG is defined recursively on this definition by:

 Base case:

jhleaf;lijWWD1; for alll 2 L:

 Constructor case:

jhbintree;G 1 ;G 2 ijWWDjG 1 jCjG 2 jC1:

For example, the size of the binary-2PTG,G, pictured in Figure 6.1, is 7.

G

G 11

win

G1,2

win

lose win

Figure 6.1 A picture of a binary treeG.

(a)Write out (using angle brackets and labelsbintree,leaf, etc.) the binary-2PTG,
G, pictured in Figure 6.1.

The value of flatten.G/forG 2 binary-2PTG is the sequence of labels inLof
the leaves ofG. For example, for the binary-2PTG,G, pictured in Figure 6.1,

flatten.G/D.win;lose;win;win/:
(b)Give a recursive definition of flatten. (You may use the operation ofconcate-
nation(append) of two sequences.)

(c)Prove by structural induction on the definitions of flatten and size that

2 
length.flatten.G//DjGjC1: (6.24)