Balanced binary tree

A binary tree whose subtree sizes or heights satisfy a stated balance condition. Recursively splitting an $n$-element sorted list into sizes $\lfloor n/2\rfloor$ and $\lceil n/2\rceil -1$ gives logarithmic height and child sizes differing by at most one. This is a static construction; ordinary binary search tree insertion does not automatically retain balance.

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\ge 2$ and strictly shorter than the input; induction proves termination and balance. This leaf-count convention is different from demanding equal subtree heights.

The condition that each binary-tree vertex has child subtrees whose node counts differ by at most one. Recursively choosing the middle entry of an index interval establishes this condition at every vertex, with exactly one allocated node per entry. No ordering assumption on the stored values is needed for the balance property or for reproducing the input's inorder sequence.