Which type of tree is defined by the condition that, for every node, the…

Concept — height balance. In a binary tree the balance factor of a node is height(left subtree) - height(right subtree), where the height of a node is the number of edges on the longest downward path from it to a leaf and an empty subtree counts as height -1. A tree is called height-balanced when this factor stays within {-1, 0, +1} at every node.

Why the bound matters. It is a local condition that has to hold at each node, not only at the root, and holding it everywhere is what forces the number of levels to grow like log n instead of n, keeping every root-to-leaf operation logarithmic.

Application. The structure defined by exactly this per-node condition is the AVL tree (Adelson-Velsky and Landis, 1962): a binary search tree in which every node carries its balance factor. After an insertion, one rebalance - a single rotation (LL, RR) or a double rotation (LR, RL) - is enough to restore the ±1 bound; after a deletion the height change can travel upward, so such a rotation may have to be applied again at several ancestors along the path to the root.

The bound is tight enough to pin the height:

1. Let N(h) be the smallest number of nodes an AVL tree of height h can have.

2. A minimal tree of height h has a root, one subtree of height h - 1, and - to stay minimal while still respecting the bound - one subtree of height h - 2, so N(h) = 1 + N(h - 1) + N(h - 2), with N(0) = 1 and N(1) = 2.

3. This Fibonacci-like recurrence solves to N(h) = F(h + 3) - 1, so the minimum node count grows exponentially in h.

4. Inverting it bounds the height of an n-node AVL tree by h ≤ 1.44 log2(n + 2), that is Θ(log n); search, insert and delete are therefore O(log n).

Contrast — what each of the other structures is defined by.

• Binary search tree: an ordering rule on keys — every key in a node’s left subtree is smaller and every key in its right subtree is larger. Nothing constrains the shape, so inserting 1, 2, 3, ..., n in that order builds a single right-going chain of height n - 1.

• Threaded binary tree: a pointer rule — a node’s null child links are replaced by threads to its inorder predecessor and successor, so an inorder traversal moves from node to node without a stack or recursion.

• Complete binary tree: a filling rule — every level except possibly the last is completely filled and the last level’s nodes are packed to the left, which is what makes the gap-free array layout (children of index i at 2i + 1 and 2i + 2) work. That shape does end up keeping the two subtree heights within one at every node, but only as a consequence of the filling rule; the tree is not defined by the height condition and need not be a search tree at all.

Result. The tree defined by the rule "for every node, the heights of the left and right subtrees differ by at most one" is the AVL tree; the other structures are defined by an ordering rule, a pointer rule, or a filling rule instead.