Suppose that during a preorder traversal of a binary tree $T$, we write down a one for each internal vertex and a zero for each leaf in the traversal, building a sequence of ones and zeros. if $T$ has $n$ leaves, the sequence will have $n$ zeros and $n-1$ ones. We call this sequence the characteristic sequence of $T$. (Such a sequence determines a unique tree.)
Find the binary tree with characteristic sequence $110100110100100$.
Prove that the last two digits in any characteristic sequence are zeros (assuming $n\geq 2$).
Prove that a binary sequence with $n$ zeros and $n-1$ ones, for some $n$ is a characteristic sequence of some binary tree if and only if the first $k$ digits of the sequence contain at least as many ones as zeros, for $1 \leq k \leq 2n-2$.
I am having trouble understanding parts (2) and (3) of this problem, although I do know how to constuct the tree in part (1).
Every non-leaf has two children. If either of the two last digits of the characteristic sequence aren't zero, then their corresponding nodes must have two children. But then digits corresponding to those children nodes must be to the right in the characteristic sequence, contradicting them being one of the last two digits.
Notice that given a characteristic sequence that defines a tree, the initial $k$ digits of that sequence also can define a unique tree where you must "cap" that sequence with either one or two zeros as appropriate. Anyways, since the characteristic sequence for any tree has $n$ zeros and $n-1$ ones, this initial segment without the cap must have at least as many ones as zeros.