Minimum number of nodes in an AVL Tree with given height using C++.

Problem statement

Given the height of an AVL tree, the task is to find the minimum number of nodes the tree can have.

If height = 0 then AVL tree can have one 1 node If height = 5 then AVL tree can have minimum 20 nodes

Algorithm

In an AVL tree, we have to maintain the height balance property, i.e. a difference in the height of the left and the right subtrees cannot be more than -1, 0 or 1 for each node. Using this property, we can create below recurrence relation −

1. If height = 0 then return 1 2. If height = 1 then return 2 3. If height > 1 then return (1 + getMinAVLNodes(h – 1) + getMinAVLNodes(h – 2))

Example

#include <iostream> using namespace std; int getMinAVLNodes(int h){    if (h < 0) {       return 0;    }    if (h == 0 || h == 1) {       return h + 1;    }    return 1 + getMinAVLNodes(h - 1) + getMinAVLNodes(h -2); } int main(){    int h = 5;    cout << "Minimum nodes for " << h << " height = " << getMinAVLNodes(h) << endl;    return 0; }

Output

When you compile and execute the above program. It generates the following output −

Minimum nodes for 5 height = 20