Given the height of an AVL tree ‘h’, the task is to find the minimum number of nodes the tree can have.
Input : H = 0
Output : N = 1
Only '1' node is possible if the height
of the tree is '0' which is the root node.
Input : H = 3
Output : N = 7
Recursive Approach : In an AVL tree, we have to maintain the height balance property, i.e. difference in the height of the left and the right subtrees can not be other than -1, 0 or 1 for each node.
We will try to create a recurrence relation to find minimum number of nodes for a given height, n(h).
- For height = 0, we can only have a single node in an AVL tree, i.e. n(0) = 1
- For height = 1, we can have a minimum of two nodes in an AVL tree, i.e. n(1) = 2
- Now for any height ‘h’, root will have two subtrees (left and right). Out of which one has to be of height h-1 and other of h-2. [root node excluded]
- So, n(h) = 1 + n(h-1) + n(h-2) is the required recurrence relation for h>=2 [1 is added for the root node]
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>
using namespace std;
int AVLnodes( int height)
{
if (height == 0)
return 1;
else if (height == 1)
return 2;
return (1 + AVLnodes(height - 1) + AVLnodes(height - 2));
}
int main()
{
int H = 3;
cout << AVLnodes(H) << endl;
}
|
Java
class GFG{
static int AVLnodes( int height)
{
if (height == 0 )
return 1 ;
else if (height == 1 )
return 2 ;
return ( 1 + AVLnodes(height - 1 ) + AVLnodes(height - 2 ));
}
public static void main(String args[])
{
int H = 3 ;
System.out.println(AVLnodes(H));
}
}
|
Python3
def AVLnodes(height):
if (height = = 0 ):
return 1
elif (height = = 1 ):
return 2
return ( 1 + AVLnodes(height - 1 ) +
AVLnodes(height - 2 ))
if __name__ = = '__main__' :
H = 3
print (AVLnodes(H))
|
C#
using System;
class GFG
{
static int AVLnodes( int height)
{
if (height == 0)
return 1;
else if (height == 1)
return 2;
return (1 + AVLnodes(height - 1) +
AVLnodes(height - 2));
}
public static void Main()
{
int H = 3;
Console.Write(AVLnodes(H));
}
}
|
PHP
<?php
function AVLnodes( $height )
{
if ( $height == 0)
return 1;
else if ( $height == 1)
return 2;
return (1 + AVLnodes( $height - 1) +
AVLnodes( $height - 2));
}
$H = 3;
echo (AVLnodes( $H ));
|
Javascript
<script>
function AVLnodes(height)
{
if (height == 0)
return 1;
else if (height == 1)
return 2;
return (1 + AVLnodes(height - 1) +
AVLnodes(height - 2));
}
let H = 3;
document.write(AVLnodes(H));
</script>
|
Time complexity O(2^n),where n is the height of the AVL tree.the reason being the function recursively calls itself twice for each level of the tree, resulting in an exponential time complexity.
Space complexity O(n),where n is the height of the AVL tree.
Tail Recursive Approach :
- The recursive function for finding n(h) (minimum number of nodes possible in an AVL Tree with height ‘h’) is n(h) = 1 + n(h-1) + n(h-2) ; h>=2 ; n(0)=1 ; n(1)=2;
- To create a Tail Recursive Function, we will maintain 1 + n(h-1) + n(h-2) as function arguments such that rather than calculating it, we directly return its value to main function.
Below is the implementation of the above approach :
C++
#include <iostream>
using namespace std;
int AVLtree( int H, int a = 1, int b = 2)
{
if (H == 0)
return 1;
if (H == 1)
return b;
return AVLtree(H - 1, b, a + b + 1);
}
int main()
{
int H = 5;
int answer = AVLtree(H);
cout << "n(" << H << ") = "
<< answer << endl;
return 0;
}
|
Java
class GFG
{
static int AVLtree( int H, int a, int b)
{
if (H == 0 )
return 1 ;
if (H == 1 )
return b;
return AVLtree(H - 1 , b, a + b + 1 );
}
public static void main(String[] args)
{
int H = 5 ;
int answer = AVLtree(H, 1 , 2 );
System.out.println( "n(" + H + ") = " + answer);
}
}
|
Python3
def AVLtree(H, a, b):
if (H = = 0 ):
return 1 ;
if (H = = 1 ):
return b;
return AVLtree(H - 1 , b, a + b + 1 );
if __name__ = = '__main__' :
H = 5 ;
answer = AVLtree(H, 1 , 2 );
print ( "n(" , H , ") = " \
, answer);
|
C#
using System;
class GFG
{
static int AVLtree( int H, int a, int b)
{
if (H == 0)
return 1;
if (H == 1)
return b;
return AVLtree(H - 1, b, a + b + 1);
}
public static void Main(String[] args)
{
int H = 5;
int answer = AVLtree(H, 1, 2);
Console.WriteLine( "n(" + H + ") = " + answer);
}
}
|
Javascript
<script>
function AVLtree(H, a, b)
{
if (H == 0)
return 1;
if (H == 1)
return b;
return AVLtree(H - 1, b, a + b + 1);
}
let H = 5;
let answer = AVLtree(H, 1, 2);
document.write( "n(" + H + ") = " + answer);
</script>
|
Time complexity O(H),where H is the height of the AVL tree being calculated.
the function makes a recursive call for each level of the AVL tree, and the maximum number of levels in an AVL tree is H.
Space complexity O(1), which is constant.
Contact Us