BST COUNT

Last Updated on March 21, 2022 by Ria Pathak

CONCEPTS USED:

Recursion,Dynamic programming.

DIFFICULTY LEVEL:

Medium.

PROBLEM STATEMENT(SIMPLIFIED):

Arnab is now given N nodes. Now he asked how many binary search trees can be formed using those N nodes.

For Example :

See original problem statement here

OBSERVATION:

The number of binary search trees can be seen as a recursive solution. i.e., Number of binary search trees = (Number of Left binary search sub-trees) (Number of Right binary search sub-trees) (Ways to choose the root)

SOLVING APPROACH:

Total number of BSTs for ‘n’ distinct keys = total number of BSTs with ‘1’ as root + total number of BSTs with ‘2’ as root + … + total number of BSTs with ‘n’ as root

Now we try to find out the value of each term on the right hand side of above equation – total number of BSTs with number ‘i’ as root? We have ‘n’ distinct keys and we have to make number ‘i’ as the root of these BSTs. In this case there would be (i-1) distinct values which would go in left sub-trees of BSTs with ‘i’ as their root and there would be (n-i) distinct values which would go in right sub-trees of BSTs with ‘i’ as their root. Because left sub-trees of these BSTs formed by (i-1) distinct keys are independent of the right sub-trees of these BSTs formed by (n-i) distinct keys, we can say that the total number of BSTs with ‘i’ as their root = total number of BSTs with (i-1) distinct keys*total number of BSTs with (n-i) distinct keys.

ALGORITHM:

In a BST, only the relative ordering between the elements matter. So, without any loss on generality, we can assume the distinct elements in the tree are 1, 2, 3, 4, …., n. Also, let the number of BST be represented by f(n) for n elements.

Now we have the multiple cases for choosing the root.

choose 1 as root, no element can be inserted on the left sub-tree. n-1 elements will be inserted on the right sub-tree.
Choose 2 as root, 1 element can be inserted on the left sub-tree. n-2 elements can be inserted on the right sub-tree.
Choose 3 as root, 2 element can be inserted on the left sub-tree. n-3 elements can be inserted on the right sub-tree.
…… Similarly, for i-th element as the root, i-1 elements can be on the left and n-i on the right.
These sub-trees are itself BST, thus, we can summarize the formula as:

f(n) = f(0)f(n-1) + f(1)f(n-2) + ………. + f(n-1)f(0)

Base cases, f(0) = 1, as there is exactly 1 way to make a BST with 0 nodes. f(1) = 1, as there is exactly 1 way to make a BST with 1 node.

f(n)=summation of (f(i-1)*f(n-i)) from i=1 to i=n.

Note:
f(n) makes 2(n-1) recursive calls, then f(n-1) makes 2(n-2) recursive calls and so on. Note that because we are storing the intermediate results, though each f(i) occurs twice while evaluating f(n), we need to compute f(i) only once which avoids exponential running time for this algorithm.

SOLUTIONS:

#include <stdio.h>
      int dp[20];
    int main()
     {
    //write your code 
    dp[1]=1,dp[0]=1;
    for(int i=2;i<12;i++)
    {int s=0;
    for(int j=1;j<=i;j++)
    {
      s+=(dp[j-1]*dp[i-j]);
    }
    dp[i]=s;
    }
    int t;
    scanf("%d",&t);
    while(t--)
    {
    int n;
    scanf("%d",&n);
    printf("%d\n",dp[n]);
    }
    return 0;
    }

#include <bits/stdc++.h>
     using namespace std;
     int dp[20];
     int main()
    { 
    dp[1]=1,dp[0]=1;
    for(int i=2;i<12;i++)
     {int s=0;
    for(int j=1;j<=i;j++)
    {
      s+=(dp[j-1]*dp[i-j]);
    }
    dp[i]=s;
    }
    int t;
    cin>>t;
    while(t--)
    {
    int n;
    cin>>n;
    cout<<dp[n]<<"\n";
    }
    return 0;
    }

import java.util.*;
    import java.io.*;
    class BinarySearchTree {   
    public static class Node{  
        int data;  
        Node left;  
        Node right;  

        public Node(int data){ 
            this.data = data;  
            this.left = null;  
            this.right = null;  
            }  
        }  
    public Node root;  

    public BinarySearchTree(){  
        root = null;  
    }  
    public int factorial(int num) {  
        int fact = 1;  
        if(num == 0)  
            return 1;  
        else {  
            while(num > 1) {  
                fact = fact * num;  
                num--;  
            }  
            return fact;  
        }  
    }  
    public int numOfBST(int key) {  
        int catalanNumber = factorial(2 * key)/(factorial(key + 1) * factorial(key));  
        return catalanNumber;  
    }  

    public static void main(String[] args) {  
        Scanner sc = new Scanner(System.in);
        int t= sc.nextInt();
        while(t-- >0 ){
            int n = sc.nextInt();
            BinarySearchTree bt = new BinarySearchTree();
        System.out.println(bt.numOfBST(n)); } 
      }  
    }  

dp = [0] * 20
dp[1]=1
dp[0]=1

for i in range(2, 12):
	
	s=0
	
	for j in range(1, i + 1):
	
		s += (dp[j - 1] * dp[i - j])
	
	dp[i] = s
	
for _ in range(int(input())):
	
	n = int(input())
	print(dp[n])

[forminator_quiz id="2104"]

So, in this blog, we have tried to explain the concept of Recursion,Dynamic programming. If you want to practice interview coding, which is curated by our expert mentors at PrepBytes, you can follow this link Interview Coding.