Find the Minimum number of nodes in an AVL Tree

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(h-1) + S(h-2) + 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 (height-1), (height-2), 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 tail-recursive function, we send (h-1) and (h-2) 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 (h-1)), and h2 (the value of  (h-2)) 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 tail-recursive function with the values, (height-1), 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

1. What are AVL Trees?
   AVL Trees are special self-balancing Binary Search Trees where the tree's height is (log₂ 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 tail-recursive 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!