What is the maximum height of an AVL tree with 12 nodes, assuming the height…

Concept: For a height-balanced (AVL) tree, the two subtrees of every node may differ in height by at most 1. Let N(h) be the minimum number of nodes needed to build an AVL tree of height h. Packing the fewest possible nodes means both subtrees are themselves minimum-node AVL trees, one of height h-1 and one of height h-2, giving the recurrence N(h) = N(h-1) + N(h-2) + 1, with base cases N(0) = 1 (a single node has height 0) and N(1) = 2.

Application: Compute the minimum-node count N(h) for increasing heights using the recurrence above:

1. N(2) = N(1) + N(0) + 1 = 2 + 1 + 1 = 4

2. N(3) = N(2) + N(1) + 1 = 4 + 2 + 1 = 7

3. N(4) = N(3) + N(2) + 1 = 7 + 4 + 1 = 12

4. N(4) = 12 exactly matches the given node count, so a height-4 AVL tree can be built with exactly 12 nodes — and no taller tree can be, since that would need more nodes than are available.

Cross-check: Check one height further: N(5) = N(4) + N(3) + 1 = 12 + 7 + 1 = 20, which needs 8 more nodes than the 12 available, confirming height 5 is out of reach. Directly counting also matches: a minimum-size height-4 tree is 1 root node + a minimum height-3 subtree (7 nodes) + a minimum height-2 subtree (4 nodes) = 1 + 7 + 4 = 12 nodes.

Result: So the maximum possible height of an AVL tree with exactly 12 nodes is 4.