Example
Sample Input: h = 5
Expected Output: 20
Sample Input: h = 0
Expected Output: 1
Approach 1: Simple Recursion
For a given AVL Tree with height ‘h’, the minimum number of nodes can be found out using the formula,
S(h) = S(h1) + S(h2) + 1, h >= 2
where h is the height of the AVL Tree.
So, we use recursion to implement this formula and find out the minimum number of nodes the AVL Tree can have.
To implement the recursive function, we do the following steps.
 Create the recursive function (say nodeCountRec()). The function takes the height of the tree as an argument.

The base case is when the height is either 0 or 1.
 In the case of 0, we return 1. Because an AVL of height 0 will have a minimum of 1 node (the root node).
 In the case of 1, we return 2. Because an AVL of height 1 will have a minimum of 2 nodes (the root node and one child node).
 We will call the recursion function for (height1), (height2), and for each recursive call, add 1 (the root node itself).
 Once the recursion is complete, we return the final answer.

The following code piece shows the recursive implementation in JAVA.
//recursion
static int nodeCountRec(int height)
{
if (height == 0)
return 1;
else if (height == 1)
return 2;
return (1 + nodeCountRec(height  1) + nodeCountRec(height  2));
}
Approach 2: Tail Recursion
To make the recursive function better, we use tail recursion. In the tailrecursive function, we send (h1) and (h2) values rather than recursion to find them.
To implement tail recursion, we do the following steps.
 Create a function (say nodeCountTailRec()) that will take the height of the tree, h1 (the value of (h1)), and h2 (the value of (h2)) as function arguments.

The base case of the tail recursion is:
 If the height is 0, return 1.
 If the height is 1, return 2.
 Call the tailrecursive function with the values, (height1), h2, and (h1+h2+1).
 Once the recursion is complete, the function returns the minimum node count.

The following code piece shows the tail recursion implementation in JAVA.
//tail recursion
static int nodeCountTailRec(int height, int h1, int h2)
{
if (height == 0)
return 1;
if (height == 1)
return h2;
return nodeCountTailRec(height  1, h2, h1 + h2 + 1);
}
Approach 3: Dynamic Programming
To overcome the recursion, we can also use Dynamic Programming. The problem is similar to finding out the n^{th} Fibonacci number. The only difference is that in every step we add 1 to the total count (for the root node).
To implement DP we do the following:
 Create a function (say nodeCountDP()) and pass the height as the function argument.

Check for height.
 If the height is 0, return 1.
 If the height is 1, return 2.
 Else, declare three variables a, b, and c. Initialize a = 1, b = 2.

Iterate from [2 … height], and,
 Set c to a+b+1.
 Swap the value of a with b.
 Swap the value of b with c.
 Once the loop is complete, return b.

The following code piece shows the DP implementation in JAVA.
//dynamic programming
static int nodeCountDP(int height)
{
if (height == 0)
return 1;
if (height == 1)
return 2;
int a = 1;
int b = 2;
int c;
for (int i = 2; i <= height; i++)
{
c = a + b + 1;
a = b;
b = c;
}
return b;
}
Java Implementation
public class AVLTrees {
//dynamic programming
static int nodeCountDP(int height)
{
if (height == 0)
return 1;
if (height == 1)
return 2;
int a = 1;
int b = 2;
int c;
for (int i = 2; i <= height; i++)
{
c = a + b + 1;
a = b;
b = c;
}
return b;
}
//tail recursion
static int nodeCountTailRec(int height, int h1, int h2)
{
if (height == 0)
return 1;
if (height == 1)
return h2;
return nodeCountTailRec(height  1, h2, h1 + h2 + 1);
}
//recursion
static int nodeCountRec(int height)
{
if (height == 0)
return 1;
else if (height == 1)
return 2;
return (1 + nodeCountRec(height  1) + nodeCountRec(height  2));
}
//main method
public static void main(String[] args)
{
int height = 6;
//recursion
System.out.println("Recursion For an AVL Tree of height " + height + " minimum number of nodes= " + nodeCountRec(height));
//tail recursion
System.out.println("Tail Recursion For an AVL Tree of height " + height + " minimum number of nodes= " + nodeCountTailRec(height, 1, 2));
//DP
System.out.println("Dynamic Programming For an AVL Tree of height " + height + " minimum number of nodes= " + nodeCountDP(height));
}
}
OUTPUT
Recursion For an AVL Tree of height 6 minimum number of nodes= 33
Tail Recursion For an AVL Tree of height 6 minimum number of nodes= 33
Dynamic Programming For an AVL Tree of height 6 minimum number of nodes= 33
Complexities
Time Complexity
 Recursive Approach: In the two recursive methods, we perform similar actions to that of finding the n^{th } Fibonacci number. So, the time complexity is Θ(ϕh), where ϕ=(1+√5)/2 is the golden ratio, where h is the height of the AVL tree.
 DP Approach: In the DP approach, we iterate in the range [2 .. height], and calculate the minimum node count. So, the time complexity will be O(h), where h is the height of the AVL tree.
Space Complexity
 Recursive Approach: For both recursions, the space complexity will be O(h), where h is the height of the AVL tree.
 DP Approach: For the DP approach, the space complexity will be O(1).
Frequently Asked Questions

What are AVL Trees?
AVL Trees are special selfbalancing Binary Search Trees where the tree's height is (log_{2 }n), where n is the number of nodes.
2. What do you mean by tail recursion?
When the last call of a function is the recursive call, that function is called a tailrecursive function. In some cases, they are the optimized version of the recursion function. To know more about tail recursion click, Tail Recursion.
Also Read  Strong number in c
Key Takeaways
To summarize the article, we learned to find the minimum number of nodes in an AVL Tree of a given height. We first saw the problem statement and a few examples. Then we saw three approaches and their Java implementation. To sum up the article, we discussed a few FAQs.
Check out this problem  Connect Nodes At Same Level
Want to increase your knowledge on recursion? Visit Recursion to read many useful articles.
Want to learn about topics like Web Technologies, Programing Fundamentals, Aptitude, DSA, and much more? Visit CN Library  Free Online Coding Resources today.
Happy Coding!