The Height of an AVL Tree

An AVL tree is a binary search tree in which every node’s two subtrees differ in height by at most one. The height of a tree is the number of edges on its longest path from the root down to a leaf.

Solution

$N (0) = 1$ , a single node. $N (1) = 2$ , a root with one child. The smallest tree of height $h$ is a root with a smallest subtree of height $h - 1$ and a smallest subtree of height $h - 2$ , so

N (h) = 1 + N (h - 1) + N (h - 2)

That gives $1, 2, 4, 7, 12, 20, 33$ , so $N (6) = 33$ .

Solution

$4$ . A tree of height $4$ needs at least $N (4) = 12$ nodes, and $15$ nodes are enough for that. A tree of height $5$ needs at least $N (5) = 20$ nodes, and $15$ nodes are not enough.

Solution

Let $N (h)$ be the fewest nodes an AVL tree of height $h$ can have. Since $N (h) = 1 + N (h - 1) + N (h - 2) > 2 N (h - 2)$ , $N (h)$ more than doubles every two levels, so $N (h) \geq 2^{h /2}$ . An AVL tree of height $h$ with $n$ nodes has $n \geq N (h) \geq 2^{h /2}$ , so $h \leq 2 lo g_{2} n$ , which is $O (lo g n)$ .