Different Shapes of AVL Possible at Height H

Intuition

For a minimal AVL Tree, we are always bound to use the minimal number of nodes, which will be used to form an AVL Tree having 'H' height. 

In a balanced tree, we are always allowed to have a maximum difference of height as one. So comparing two balanced trees, in the first tree, the height of both the left subtree as well as right subtree are equal but in the second tree, the height of the left subtree is one higher than the height of the right subtree. Now if we compare both trees, the second tree will have fewer nodes.  

Thus to minimize the nodes of the AVL Tree with height ‘H’ greater than one, we will maintain a difference of heights between the left and right subtree.

For example

AVL Tree with h = 2: 

Fig a. AVL Tree with equal heights of left and right subtree of root

After we remove the red color nodes from Fig a. 

Fig b. AVL Tree with having a difference between heights of left and right subtree of root

So from the above example, we can realize that to have a minimal AVL Tree, there needs to be a difference between the heights of the left and right subtree. But to have it balanced, we can only afford a maximum difference of one.

Let’s understand the further approach.

Approach

From the above intuition we can generalize that the AVL Tree of height 'H' will be of the form: 

Lets say count(h) represents the number of total possible shapes of  AVL Trees of height 'H'. Thus generalizing the formula:

   count(h) = count(h-1) x count(h-2) + count(h-2) x count(h-1) = 2 x count(h-1) x count(h-2)

Algorithm

• As discussed above, the vector count can be used to store the number of possible trees
• We can generate a recursive function findPossibleAVL() taking 'H' as its argument, which will return the number of possible shapes of AVL trees with height 'H’.
• In function findPossibleAVL(), we can find the result as:

findPossibleAVL(h) = 2 x findPossibleAVL(h-1) x findPossibleAVL(h-2)     

The implementation of the above approach is shown in the below program.

Check out this problem - Count Inversions

Program

// Program to find possible AVL Trees wit height 'H'.
#include <iostream>
#include <vector>

using namespace std;

// Function to find number of AVL Trees.
int findPossibleAVL(int H, vector<int>& count)
{
      // If already calculated.
      if (count[H] != -1)
            return count[H];

      // Doing the recursive call to find result for H-1 and H-2.
      count[H] = 2 * findPossibleAVL(H - 1, count) * findPossibleAVL(H - 2, count);

      // Returning the result.
      return count[H];
}

// Main function.
int main()
{
      // Input of height of AVL Tree.
      int H; cin >> H;

      // Vector to store number of possible AVL Trees.
      vector<int> count(max(2, H + 1), -1);

      // Base cases.
      count[0] = 1;
      count[1] = 2;

      // Output for the final result.
      cout << "Number of possible AVL Trees: " << findPossibleAVL(H, count);

      return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Example

Input

3

Output

Number of possible AVL Trees: 16

Complexity Analysis

Time Complexity: O(H), where H is the height of the tree.

Explanation: 

The recursive function will store the number of possible shapes of AVL Trees for every height, from 0 to H in O(1), adding up to O(H).

Space Complexity: O(H), where H is the height of the tree.

Explanation:

The vector used to store the number of possible shapes of AVL Trees for H heights accounts for O(h) space.

Key Takeaways

The blog discussed an interesting problem related to AVL Trees, ‘Different Shapes of AVL Possible at Height h’. The intuition, approach, and algorithm, along with code in C++ mentioned above are helpful to understand the problem as well as its solution. You can practice more such problems from questions related to Trees.

If you want to learn more before jumping into practicing, head over to our library section for many such interesting blogs. Keep learning.

Happy Coding!