Let T be a complete binary tree with the vertices of T ordered by a preorder traversal. This traversal assigns the label 1 to all internal vertices of T and the label 0 to each leaf. The sequence of 0's and l's that results from the preorder traversal of T is called the tree's characteristic sequence.
(a) Find the characteristic sequence for the complete binary tree shown in Fig. 12.17.
(b) Determine the complete binary trees for the characteristic sequences
(i) 1011001010100 and
(ii) 1011110000101011000.
(c) What are the last two symbols in the characteristic sequence for all complete binary trees? Why?