Improve Article
Save Article
Like Article
Given the height of an AVL tree ‘h’, the task is to find the minimum number of nodes the tree can have. Examples : 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). Below is the implementation of the above approach: #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; }
Tail Recursive Approach :
Below is the implementation of the above approach :
|