= Leaf-balanced binary tree
A <leaf-labelled binary tree> is leaf-balanced when the leaf counts of the two subtrees at every internal node differ by at most one. Splitting a finite nonempty <list> into pieces of sizes $\lfloor n/2\rfloor$ and $\lceil n/2\rceil$ and applying the same construction recursively preserves the original leaf order and gives this balance condition. Both pieces are nonempty for $n\ge2$ and strictly shorter than the input; <induction> proves termination and balance. This leaf-count convention is different from demanding equal subtree heights.
Back to article page
