Leaves of which of the following trees are at the same level?

Concept — perfect height balance. A tree is perfectly height-balanced when every root-to-leaf path has exactly the same length, so all leaves sit on one level. This is a consequence of the growth rule, not of the number of nodes: it holds only when the rule that adds a new level adds it to every root-to-leaf path at the same instant.

Two different balance notions must be kept apart. A per-node bound on subtree heights — |hL − hR| ≤ 1 at every node — keeps the height logarithmic but still allows leaves at different depths. A bottom-up growth rule, in which new levels can appear only above the current root, forces every leaf to the same depth.

Application — how a B-tree of order m grows:

1. An empty B-tree has a single node that is also its only leaf, so the invariant "all leaves on one level" holds at the start.

2. Every insertion starts at a leaf. If that leaf holds fewer than m − 1 keys, the key is simply stored and no node changes depth.

3. If the leaf is full, it splits into two nodes at the same depth and its median key is promoted into the parent. Both halves remain leaves on the level they were already on.

4. If the promotion overflows the parent, that node splits and promotes in turn. The cascade travels upward only, so no leaf is pushed down relative to another.

5. If the cascade reaches a full root, the root splits and a brand-new root is created above it. The height grows by one at the top, which deepens every leaf by exactly one, simultaneously.

6. By induction over the insertions, the invariant is never broken: all leaves of a B-tree lie on the same level at all times. Deletion preserves it symmetrically, by merging siblings and shrinking the tree at the root.

Cross-check — concrete counter-examples for the other structures:

• Binary tree: take the tree whose root has a leaf as its left child, while its right child carries a single leaf child of its own. That one tree has a leaf at depth 1 and a leaf at depth 2, and every node still has at most two children, so it is a perfectly valid binary tree.

• AVL tree: inserting 1, 2, 3, 4 yields root 2 with children 1 and 3, and 4 as the right child of 3. Leaf 1 is at depth 1 and leaf 4 is at depth 2, yet every node satisfies the AVL balance factor.

• Expression tree: a + b × c places a at depth 1 and b and c at depth 2, because the shape follows operator precedence rather than any balance rule.

Result: the structure whose leaves are guaranteed to be at the same level is the B-tree.