Count of BSTs with N nodes having height at least K
Given two positive integers N and K, the task is to find the number of binary search trees (BST) with N nodes of height greater than or equal to K.
Note: Here height refers to the maximum depth of the BST.
Examples:
Input: N = 3, K = 3
Output: 4
Explanation:
There are 4 possible binary search trees with height greater than or equal to K.1 1 3 3
\ \ / /
2 3 2 1
\ | / \
3 2 1 2Input: N = 4, K = 2
Output: 14
Approach: This problem can be solved using recursion. Follow the steps below to solve the problem:
- Base Case: if N is equal to 1 then return 1.
- Initialize a variable countBsts as 0 to store the number of valid BSTs.
- Iterate in the range [1, N] using the variable i:
- If i-1 and N-i is greater than equal to K, then:
- Recursively call the function for left subtree, with nodes as i ā 1 and height as K ā 1 which will find the number of ways to create left subtree.
- Recursively call the function for right subtree with nodes as N ā i and height as K ā 1 which will find the number of ways to create right subtree.
- Add the result in countBsts.
- If i-1 and N-i is greater than equal to K, then:
- After completing the above steps, print the countBsts.
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to find the number of BST's // with N nodes of height greater than // or equal to K int numOfBst( int n, int k) { if (n <= 1) { return 1; } // Store number of valid BSTs int countBsts = 0; // Traverse from 1 to n for ( int i = 1; i <= n; i++) { // If Binary Tree with height greater // than K exist if (i - 1 >= k or n - i >= k) countBsts += numOfBst(i - 1, k - 1) * numOfBst(n - i, k - 1); } // Finally, return the countBsts return countBsts; } // Driver Code int main() { // Given Input int n = 4; int k = 2; // Function call to find the number // of BSTs greater than k cout << numOfBst(n, k - 1) << endl; return 0; } |
Java
// Java program for the above approach import java.io.*; class GFG { // Function to find the number of BST's // with N nodes of height greater than // or equal to K static int numOfBst( int n, int k) { if (n <= 1 ) { return 1 ; } // Store number of valid BSTs int countBsts = 0 ; // Traverse from 1 to n for ( int i = 1 ; i <= n; i++) { // If Binary Tree with height greater // than K exist if (i - 1 >= k || n - i >= k) countBsts += numOfBst(i - 1 , k - 1 ) * numOfBst(n - i, k - 1 ); } // Finally, return the countBsts return countBsts; } // Driver Code public static void main(String[] args) { // Given Input int n = 4 ; int k = 2 ; // Function call to find the number // of BSTs greater than k System.out.println(numOfBst(n, k - 1 )); } } // This code is contributed by potta lokesh. |
Python3
# python 3 program for the above approach # Function to find the number of BST's # with N nodes of height greater than # or equal to K def numOfBst(n, k): if (n < = 1 ): return 1 # Store number of valid BSTs countBsts = 0 # Traverse from 1 to n for i in range ( 1 , n + 1 , 1 ): # If Binary Tree with height greater # than K exist if (i - 1 > = k or n - i > = k): countBsts + = numOfBst(i - 1 , k - 1 ) * numOfBst(n - i, k - 1 ) # Finally, return the countBsts return countBsts # Driver Code if __name__ = = '__main__' : # Given Input n = 4 k = 2 # Function call to find the number # of BSTs greater than k print (numOfBst(n, k - 1 )) # This code is contributed by bgangwar59. |
C#
// C# program for the above approach using System; class GFG { // Function to find the number of BST's // with N nodes of height greater than // or equal to K static int numOfBst( int n, int k) { if (n <= 1) { return 1; } // Store number of valid BSTs int countBsts = 0; // Traverse from 1 to n for ( int i = 1; i <= n; i++) { // If Binary Tree with height greater // than K exist if (i - 1 >= k || n - i >= k) countBsts += numOfBst(i - 1, k - 1) * numOfBst(n - i, k - 1); } // Finally, return the countBsts return countBsts; } // Driver code static void Main() { // Given Input int n = 4; int k = 2; // Function call to find the number // of BSTs greater than k Console.WriteLine(numOfBst(n, k - 1)); } } // This code is contributed by divyeshrabadiya07. |
Javascript
<script> // JavaScript program for the above approach // Function to find the number of BST's // with N nodes of height greater than // or equal to K function numOfBst(n, k) { if (n <= 1) { return 1; } // Store number of valid BSTs let countBsts = 0; // Traverse from 1 to n for (let i = 1; i <= n; i++) { // If Binary Tree with height greater // than K exist if (i - 1 >= k || n - i >= k) countBsts += numOfBst(i - 1, k - 1) * numOfBst(n - i, k - 1); } // Finally, return the countBsts return countBsts; } // Driver Code // Given Input let n = 4; let k = 2; // Function call to find the number // of BSTs greater than k document.write(numOfBst(n, k - 1) + "<br>" ); // This code is contributed by Potta Lokesh </script> |
14
Time Complexity: O(2n)
Auxiliary Space: O(1)