= Solution
A value-bearing <perfect binary tree> has size $w=2^{h+1}-1$, and the next size is $2w+1$. Suppose two size-$w$ trees have at least one smaller tree before them. The portion represented by these trees and that nonempty preceding portion has at least $2w+1$ elements. The greedy choice would have used a larger <perfect binary tree> instead, contradicting the specified representation. Three size-$w$ trees are likewise impossible, since $3w\geq2w+1$. Therefore \b[the only possible repeated size is a pair at the beginning]. This is the representation invariant of a <skew-binary random-access list>.
Back to article page
