$(10$ points$)$ Let $T$ be a binary tree. Perform a Pre$-$Order Traversal of $T$ and

write down a sequence of ones and zeroes as we pass each vertex. We start

with the empty sequence. When we pass an internal vertex we append a $"1"$

to the sequence, and when we pass a leaf we append a $"0"$ to the sequence. We

call this sequence the characteristic sequence of a binary tree and we denote

it $(T).$

$($a$)$ Find the binary tree with $(T)=110100110100100.$

$($b$)$ Assume the order of $T$ is at least two, then show that he last two digits

of $(T)$ are always $00.$

$($c$)$ Show that a binary sequence with $k$ zeros and $k-1$ ones is a the characteristic sequence of some binary tree if and only iff the first $d$ digits of

the sequence contain at least as many ones as zeros for $1d2k-2.$