Given two integers N and H, the task is to find the count of distinct Binary Search Trees consisting of N nodes where the maximum depth or height of the tree is equal to H.
Note: The height of BST with only the root node is 0.
Examples:
Input: N = 2, H = 1
Output: 2
Explanation: The two BST’s are :
BST’s of height H = 1 and nodes N = 2
Input: N = 3, H = 2
Output: 4
Explanation: The four BST are :BST’s of height H = 2 and nodes N = 3
Naive Approach: The problem can be solved using Recursion which can be memoized to obtain a Dynamic Programming solution based on the following idea:
The problem can be efficiently solved by finding the count of BST’s having maximum depth upto H (i.e., [0 – H]) instead of exactly H.
Let f(N, H) represent the count of BST’s consisting of ‘N’ nodes and having maximum depth upto ‘H’. Then the solution for the above problem: count of BST’s having maximum depth of exactly ‘H’ is equal to f(N, H) – f(N, H – 1).
Follow the illustration below for a better understanding.
Illustration:
Consider: N = 3, H = 2
The answer for this example is : count of BST’s of maximum depth upto 2 – count of BST’s of maximum depth upto 1.
- Count of BST’s of maximum depth upto 2 is 5, they are:
5 – BST’s of maximum depth upto 2
- Count of BST’s of maximum depth upto 1 is 1, it is :
1 – BST of maximum depth upto 1
- Hence the count of BST’s of maximum depth equal to ‘2’ is 4.
Follow the steps mentioned below to solve the problem.
- The count of BST with Node i as root Node is equal to product of count of BST’s of left subtree formed by nodes 1 to i-1 and right subtree formed by nodes i+1 to N.
- In order to find the count of BST of left subtree, we can recursively call the same function for depth H-1 and N=i – 1. To find the count of BST of right subtree, recursively call the function for depth H-1 and N=N-i.
- Loop over all values of i from [1, N] as root node and add the product of count of left and right subtree to the result.
Time Complexity: O(N * 2N)
Auxiliary Space: O(1)
Efficient Approach: The above approach can be optimized by using Dynamic Programming because the above problem has Overlapping subproblems and an Optimal substructure. The subproblems can be stored in dp[][] table memoization where dp[N][H] stores the count of BST of maximum depth up to H consisting of N nodes. Follow the steps below to solve the problem:
- Initialize a global multidimensional array dp[105][105] with all values as -1 that stores the result of each recursive call.
- Define a recursive function, say countOfBST(N, H) and perform the following steps.
- Case 1: If N = 0, return 1.
- Case 2: If H = 0, return true if N = 1.
- If the result of the state dp[N][H] is already computed, return this value dp[N][H].
- Iterate over the range [1, N] using the variable ‘i‘ as root and perform the following operations.
- Multiply the value of recursive functions countOfBST(i – 1, H – 1) and countOfBST(N – i, H – 1). The two functions calculate the count of BST for the left and the right subtree respectively.
- Add the term to the final answer which stores the total count of BSTs possible for all roots from [1, N].
- Print the value returned by the function countOfBST(N, H).
Below is the implementation of the above approach :
C++
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;// Declaring a dp-arrayint dp[105][105];const int mod = 1000000007;// Function to find the count of// BST upto height 'H' consisting// of 'N' nodes.int countOfBST(int N, int H){ // Base Case1 : If N == 0, return // 1 as a valid BST has been formed if (N == 0) { return 1; } // Base Case2 : If H == 0, return true // if N == 1 if (H == 0) { return N == 1; } // If the current state has already // been computed, then return it. if (dp[N][H] != -1) { return dp[N][H]; } // Initialize answer to 0. int ans = 0; // Iterate over all numbers from // [1, N], with 'i' as root. for (int i = 1; i <= N; ++i) { // Call the recursive functions to // find count of BST of left and right // subtrees. Add the product of // both terms to the answer. ans += (countOfBST(i - 1, H - 1) * 1LL * countOfBST(N - i, H - 1)) % mod; // Take modulo 1000000007 ans %= mod; } // Return ans return dp[N][H] = ans;}// Utility function to find the count// of BST upto height 'H' consisting// of 'N' nodes.int UtilCountOfBST(int N, int H){ // Initialize dp-array with -1. memset(dp, -1, sizeof dp); // If height is 0, return true if // only one node is present. if (H == 0) { return (N == 1); } // Function call. return (countOfBST(N, H) - countOfBST(N, H - 1) + mod) % mod;}// Driver codeint main(){ // Number of nodes int N = 3; // Height of tree int H = 2; cout << UtilCountOfBST(N, H) << endl; return 0;} |
Java
// Java implementation of above approachimport java.io.*;import java.util.*;class GFG { // Declaring a dp-array static int[][] dp = new int[105][105]; static int mod = 1000000007; // Function to find the count of // BST upto height 'H' consisting // of 'N' nodes. static int countOfBST(int N, int H) { // Base Case1 : If N == 0, return // 1 as a valid BST has been formed if (N == 0) { return 1; } // Base Case2 : If H == 0, return true // if N == 1 if (H == 0) { if (N == 1) return 1; return 0; } // If the current state has already // been computed, then return it. if (dp[N][H] != -1) { return dp[N][H]; } // Initialize answer to 0. int ans = 0; // Iterate over all numbers from // [1, N], with 'i' as root. for (int i = 1; i <= N; ++i) { // Call the recursive functions to // find count of BST of left and right // subtrees. Add the product of // both terms to the answer. ans += (countOfBST(i - 1, H - 1) * countOfBST(N - i, H - 1)) % mod; // Take modulo 1000000007 ans %= mod; } // Return ans dp[N][H] = ans; return dp[N][H]; } // Utility function to find the count // of BST upto height 'H' consisting // of 'N' nodes. static int UtilCountOfBST(int N, int H) { // Initialize dp-array with -1. for (int i = 0; i < 105; i++) for (int j = 0; j < 105; j++) dp[i][j] = -1; // If height is 0, return true if // only one node is present. if (H == 0) { if (N == 1) return 1; return 0; } // Function call. return (countOfBST(N, H) - countOfBST(N, H - 1) + mod) % mod; } // Driver Code public static void main(String[] args) { // Number of nodes int N = 3; // Height of tree int H = 2; System.out.print(UtilCountOfBST(N, H)); }}// This code is contributed by code_hunt. |
Python3
# python3 code to implement the approach# Declaring a dp-arraydp = [[-1 for _ in range(105)] for _ in range(105)]mod = 1000000007# Function to find the count of# BST upto height 'H' consisting# of 'N' nodes.def countOfBST(N, H): # Base Case1 : If N == 0, return # 1 as a valid BST has been formed if (N == 0): return 1 # Base Case2 : If H == 0, return true # if N == 1 if (H == 0): return N == 1 # If the current state has already # been computed, then return it. if (dp[N][H] != -1): return dp[N][H] # Initialize answer to 0. ans = 0 # Iterate over all numbers from # [1, N], with 'i' as root. for i in range(1, N+1): # Call the recursive functions to # find count of BST of left and right # subtrees. Add the product of # both terms to the answer. ans += (countOfBST(i - 1, H - 1) * countOfBST(N - i, H - 1)) % mod # Take modulo 1000000007 ans %= mod # Return ans dp[N][H] = ans return dp[N][H]# Utility function to find the count# of BST upto height 'H' consisting# of 'N' nodes.def UtilCountOfBST(N, H): # Initialize dp-array with -1. # If height is 0, return true if # only one node is present. if (H == 0): return (N == 1) # Function call. return (countOfBST(N, H) - countOfBST(N, H - 1) + mod) % mod# Driver codeif __name__ == "__main__": # Number of nodes N = 3 # Height of tree H = 2 print(UtilCountOfBST(N, H)) # This code is contributed by rakeshsahni |
C#
// C# code to implement the approachusing System;class GFG { // Declaring a dp-array static int[, ] dp = new int[105, 105]; const int mod = 1000000007; // Function to find the count of // BST upto height 'H' consisting // of 'N' nodes. static int countOfBST(int N, int H) { // Base Case1 : If N == 0, return // 1 as a valid BST has been formed if (N == 0) { return 1; } // Base Case2 : If H == 0, return true // if N == 1 if (H == 0) { if (N == 1) return 1; return 0; } // If the current state has already // been computed, then return it. if (dp[N, H] != -1) { return dp[N, H]; } // Initialize answer to 0. int ans = 0; // Iterate over all numbers from // [1, N], with 'i' as root. for (int i = 1; i <= N; ++i) { // Call the recursive functions to // find count of BST of left and right // subtrees. Add the product of // both terms to the answer. ans += (countOfBST(i - 1, H - 1) * countOfBST(N - i, H - 1)) % mod; // Take modulo 1000000007 ans %= mod; } // Return ans dp[N, H] = ans; return dp[N, H]; } // Utility function to find the count // of BST upto height 'H' consisting // of 'N' nodes. static int UtilCountOfBST(int N, int H) { // Initialize dp-array with -1. for (int i = 0; i < 105; i++) for (int j = 0; j < 105; j++) dp[i, j] = -1; // If height is 0, return true if // only one node is present. if (H == 0) { if (N == 1) return 1; return 0; } // Function call. return (countOfBST(N, H) - countOfBST(N, H - 1) + mod) % mod; } // Driver code public static void Main() { // Number of nodes int N = 3; // Height of tree int H = 2; Console.Write(UtilCountOfBST(N, H)); }}// This code is contributed by ukasp. |
Javascript
<script> // JavaScript code for the above approach // Declaring a dp-array let dp = new Array(105); for (let i = 0; i < dp.length; i++) { dp[i] = new Array(105).fill(-1); } let mod = 1000000007; // Function to find the count of // BST upto height 'H' consisting // of 'N' nodes. function countOfBST(N, H) { // Base Case1 : If N == 0, return // 1 as a valid BST has been formed if (N == 0) { return 1; } // Base Case2 : If H == 0, return true // if N == 1 if (H == 0) { return N == 1; } // If the current state has already // been computed, then return it. if (dp[N][H] != -1) { return dp[N][H]; } // Initialize answer to 0. let ans = 0; // Iterate over all numbers from // [1, N], with 'i' as root. for (let i = 1; i <= N; ++i) { // Call the recursive functions to // find count of BST of left and right // subtrees. Add the product of // both terms to the answer. ans += (countOfBST(i - 1, H - 1) * 1 * countOfBST(N - i, H - 1)) % mod; // Take modulo 1000000007 ans %= mod; } // Return ans return dp[N][H] = ans; } // Utility function to find the count // of BST upto height 'H' consisting // of 'N' nodes. function UtilCountOfBST(N, H) { // If height is 0, return true if // only one node is present. if (H == 0) { return (N == 1); } // Function call. return (countOfBST(N, H) - countOfBST(N, H - 1) + mod) % mod; } // Driver code // Number of nodes let N = 3; // Height of tree let H = 2; document.write(UtilCountOfBST(N, H) + '<br>');// This code is contributed by Potta Lokesh </script> |
Output
4
Time Complexity: O(N2 * H)
Auxiliary Space: O(N * H)
Efficient approach : Using DP Tabulation method ( Iterative approach )
The approach to solve this problem is same but DP tabulation(bottom-up) method is better then Dp + memorization(top-down) because memorization method needs extra stack space of recursion calls.
Steps to solve this problem :
- Create a table to store the solution of the subproblems.
- Initialize the table with base cases
- Fill up the table iteratively
- Return the final solution
Implementation :
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;const int mod = 1000000007;// Function to find the count of// BST upto height 'H' consisting// of 'N' nodes.int countOfBST(int N, int H){ // Initialize dp-array int dp[N + 1][H + 1]; memset(dp, 0, sizeof(dp)); // Base Case1 : If N == 0, return // 1 as a valid BST has been formed for (int i = 0; i <= H; ++i) { dp[0][i] = 1; } // Base Case2 : If H == 0, return true // if N == 1 for (int i = 1; i <= N; ++i) { dp[i][0] = (i == 1); } // Iterate over all nodes and height for (int i = 1; i <= N; ++i) { for (int j = 1; j <= H; ++j) { for (int k = 1; k <= i; ++k) { dp[i][j] = (dp[i][j] + (dp[k - 1][j - 1] * 1LL * dp[i - k][j - 1]) % mod) % mod; } } } // Return ans return dp[N][H];}// Utility function to find the count// of BST upto height 'H' consisting// of 'N' nodes.int UtilCountOfBST(int N, int H){ if (H == 0) { return (N == 1); } // Function call. return ((countOfBST(N, H) - countOfBST(N, H - 1) + mod) % mod);}// Driver codeint main(){ // Number of nodes int N = 3; // Height of tree int H = 2; cout << UtilCountOfBST(N, H) << endl; return 0;}// this code is contributed by bhardwajji |
Java
// Java program for the above approachpublic class CountOfBST { static final int MOD = 1000000007;// Function to find the count of// BST upto height 'H' consisting// of 'N' nodes.public static int countOfBST(int N, int H) { // Initialize dp-array int[][] dp = new int[N + 1][H + 1]; // Base Case1 : If N == 0, return // 1 as a valid BST has been formed for (int i = 0; i <= H; i++) { dp[0][i] = 1; } // Base Case2 : If H == 0, return true // if N == 1 for (int i = 1; i <= N; i++) { dp[i][0] = (i == 1) ? 1 : 0; } // Iterate over all nodes and height for (int i = 1; i <= N; i++) { for (int j = 1; j <= H; j++) { for (int k = 1; k <= i; k++) { dp[i][j] = (dp[i][j] + (dp[k - 1][j - 1] * dp[i - k][j - 1]) % MOD) % MOD; } } } // Return answer return dp[N][H];}// Utility function to find the count// of BST upto height 'H' consisting// of 'N' nodes.public static int UtilCountOfBST(int N, int H) { if (H == 0) { return (N == 1) ? 1 : 0; } // Function call return ((countOfBST(N, H) - countOfBST(N, H - 1) + MOD) % MOD);}// Driver codepublic static void main(String[] args) { // Number of nodes int N = 3; // Height of tree int H = 2; // Printing the result System.out.println(UtilCountOfBST(N, H)); }} |
Python3
# Python program for the above approachMOD = 1000000007# Function to find the count of# BST upto height 'H' consisting# of 'N' nodes.def countOfBST(N: int, H: int) -> int: # Initialize dp-array dp = [[0 for j in range(H+1)] for i in range(N+1)] # Base Case1 : If N == 0, return # 1 as a valid BST has been formed for i in range(H+1): dp[0][i] = 1 # Base Case2 : If H == 0, return true # if N == 1 for i in range(1, N+1): dp[i][0] = 1 if i == 1 else 0 # Iterate over all nodes and height for i in range(1, N+1): for j in range(1, H+1): for k in range(1, i+1): dp[i][j] = (dp[i][j] + (dp[k - 1][j - 1] * dp[i - k][j - 1]) % MOD) % MOD # Return ans return dp[N][H]# Utility function to find the count# of BST upto height 'H' consisting# of 'N' nodes.def UtilCountOfBST(N: int, H: int) -> int: if H == 0: return 1 if N == 1 else 0 # Function call. return ((countOfBST(N, H) - countOfBST(N, H - 1) + MOD) % MOD)# Driver codeif __name__ == "__main__": # Number of nodes N = 3 # Height of tree H = 2 print(UtilCountOfBST(N, H)) |
C#
using System;public class CountOfBST { const int MOD = 1000000007; // Function to find the count of // BST upto height 'H' consisting // of 'N' nodes. public static int Count(int N, int H) { // Initialize dp-array int[,] dp = new int[N+1, H+1]; // Base Case1 : If N == 0, return // 1 as a valid BST has been formed for (int i = 0; i <= H; i++) { dp[0, i] = 1; } // Base Case2 : If H == 0, return true // if N == 1 for (int i = 1; i <= N; i++) { dp[i, 0] = (i == 1) ? 1 : 0; } // Iterate over all nodes and height for (int i = 1; i <= N; i++) { for (int j = 1; j <= H; j++) { for (int k = 1; k <= i; k++) { dp[i, j] = (dp[i, j] + (dp[k - 1, j - 1] * dp[i - k, j - 1]) % MOD) % MOD; } } } // Return ans return dp[N, H]; } // Utility function to find the count // of BST upto height 'H' consisting // of 'N' nodes. public static int UtilCount(int N, int H) { if (H == 0) { return (N == 1) ? 1 : 0; } // Function call. return ((Count(N, H) - Count(N, H - 1) + MOD) % MOD); } // Driver code public static void Main() { // Number of nodes int N = 3; // Height of tree int H = 2; Console.WriteLine(UtilCount(N, H)); }} |
Javascript
const MOD = 1000000007;/** * Function to find the count of BST upto height 'H' * consisting of 'N' nodes. * * @param {number} N - The number of nodes. * @param {number} H - The height of the tree. * @returns {number} The count of BST. */function countOfBST(N, H) { // Initialize dp-array const dp = Array.from({ length: N + 1 }, () => Array.from({ length: H + 1 }, () => 0) ); // Base Case1 : If N == 0, return // 1 as a valid BST has been formed for (let i = 0; i <= H; i++) { dp[0][i] = 1; } // Base Case2 : If H == 0, return true // if N == 1 for (let i = 1; i <= N; i++) { dp[i][0] = i === 1 ? 1 : 0; } // Iterate over all nodes and height for (let i = 1; i <= N; i++) { for (let j = 1; j <= H; j++) { for (let k = 1; k <= i; k++) { dp[i][j] = ((dp[i][j] + ((dp[k - 1][j - 1] * dp[i - k][j - 1]) % MOD)) % MOD); } } } // Return ans return dp[N][H];}/** * Utility function to find the count of BST upto height 'H' * consisting of 'N' nodes. * * @param {number} N - The number of nodes. * @param {number} H - The height of the tree. * @returns {number} The count of BST. */function UtilCountOfBST(N, H) { if (H === 0) { return N === 1 ? 1 : 0; } // Function call. return ((countOfBST(N, H) - countOfBST(N, H - 1) + MOD) % MOD);}// Driver codeif (require.main === module) { // Number of nodes const N = 3; // Height of tree const H = 2; console.log(UtilCountOfBST(N, H));} |
Output
4
Time Complexity: O(N2 * H)
Auxiliary Space: O(N * H)
Share your thoughts in the comments
