1. (a) A B A C F C G H G C A D E D A
   (b) 0 1 0 1 2 1 2 3 2 1 0 1 2 1 0
   (c)         ^^^^^^^^^^^^^^^

2.
          1
        /   \
      /       \
    /           \
  3               5*
    \           /   \
      6       9*     16
    /   \       \      \
  13     12       11    17
                /
              19

The two nodes are marked with asterisks (*).

3. (a) 128. Each block has seven consecutive pairs, so there are 2^7 = 128 choices for whether to go up or down at each pair.

(b) 128*8*8 = 2^13 = 8192 cells

(c) The only useful entries are the ones where the starting position is less than or equal to the ending position. There are 8+7+6+5+4+3+2+1=8*9/2 = 36 valid combinations, out of 8*8=64 choices for the start and end. So 28/64 ~ 44% of the array is wasted.

4.
      A
    / 
  B
    \
      C
    /   \
  /       \
F           D
  \       /
    G   E
  /
H