Question

What is the maximum height of any avl tree with 7 nodes? Assume that the height of a tree with a single node is 0.

Answer 1

Answer:

Minimum Nodes in an AVL tree with height n is H(n)=H(n−1)+H(n−2)+1. H(0)=1. H(3)=H(2)+H(1)+1=4+2+1=7. So, the max height with 7 nodes is 3.

Answer 2

Answer:

The maximum height of an AVL tree with 7 nodes is 3

Explanation:

An AVL tree is a self-balancing binary search tree

In an AVL tree

The heights of the two-child subtrees of any node differ by at most one

If at any time they differ by more than one, rebalancing is done to restore this property

Formula to find the maximum height of an AVL tree is

N(H) = N(H-1) + N(H-2) + 1 →(1)

H = Height

N(H) = Minimum number of nodes in the AVL tree

Let's consider

Put H = 0, 1, 2, 3,... in the formula (1)

Base conditions: N(0) = 1, N(1) = 2

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

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

N(2) = 2 + 1 + 1

N(2) = 4

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

N(3) = N(2) + N(1) + 1

N(3) = 4 + 2 + 1

N(3) = 7    

Therefore the maximum height of an AVL tree with 7 nodes is 3