For this question, the adversary wants to keep things as
sparse as possible.  This would mean that for a tree of
height h, one of the sub-trees must have height h-1 but
the other two sub-trees could each have height only h-2.