Consider the following AVL tree: root = 60; left child of 60 = 50; right child of 60 = 70; right child of 70 = 80 (a balanced AVL tree of height 2).
What is the maximum number of nodes that can be inserted in the following AVL tree without changing its height?

Explanation

The given AVL tree has height 2 (root 60 at level 0, 50 and 70 at level 1, 80 at level 2), and a binary tree of height 2 can hold at most 2³−1 = 7 nodes in total. The tree currently has only 4 nodes (60, 50, 70, 80), occupying just one of the four possible level-2 slots (the right child of 70). The three remaining level-2 slots — the left and right children of 50, and the left child of 70 — can each receive one new leaf node without increasing the height beyond 2 and without violating the AVL balance property. Hence at most 3 more nodes can be inserted while keeping the height unchanged.