Question

Form a recurrence relation for the minimum number of full nodes F(h) in a AVL tree. A node is full if it has exactly two children

Answer 1

In an AVL tree, the balance at every node must be maintained, i.e the absolute difference in the height of the left and the right subtrees can be at most 1.

Let N(h) be the minimum number of nodes in an AVL tree for a given height h.

The base conditions are

a) For h = 0, only 1 node is in the AVL tree; N(0) = 1

b) For h = 1, minimum of 2 nodes are in the AVL tree; N(1) = 2

For a given height h, one subtree is of height h-1 and the other can be at most h-2 after excluding the root node.

Hence N(h) = 1 + N(h-1) + N(h-2), h>= 2; is the recurrence relation.

Python Code Snippet. (For h = 3, the expected answer is 7)