Past exam of the year 1 of the computer science course of the University of Oxford / 2022 / Functional programming, design and analysis of algorithms (resit) / 2 / a / 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\ge 2w+1$. Therefore the only possible repeated size is a pair at the beginning. This is the representation invariant of a skew-binary random-access list.