**Number of binary search trees with n nodes**

Given a number N, calculate number of binary search trees with n nodes, means BSTs that can be formed using number 1 to N as nodes.

Let’s take an example and work out the rule. What if there is only one node i.e N =1. There is only one tree possible with given node as root node and no children.

How about we have N=2, that is we have two nodes (1 and 2). Following are possible trees we can form using these two nodes.

Now let’s take N =3. Following trees can be formed using (1,2 and 3) as nodes.

Look closely, and see that every node becomes root at some point of time. And when a node becomes root, all elements which are greater than that node can form only right subtree and similarly, numbers less than root, they can form only left subtree.

So for each node* i* as root, consider that all nodes on its left side ( from 1 to i-1 ) can form left subtree. Again root of that left sub tree can be any one of* i-1* nodes. Getting some idea? Yes, it’s getting recursive. Same is true for right side for numbers

*i+1 to N*.

Calculate number of left subtrees possible with given node i , call it *l*.

Then, calculate number of right subtrees possible with number i+1 to N and call it *r***.** For each left subtree, there are r right subtrees with given root node.

So total number of trees which can be formed using *i *as root will be *(l * r).*

Consider each node as root node and calculate number of left and right subtrees possible. Add them together and we come to our solution 🙂

Simple way to check if answer for program is correct or not, calculate a number called as Catalan number. Calculate Nth Catalan number. Mathematically, Catalan number can be represented as

## Code to find number of binary search tree with N nodes

#include<stdio.h> int number_of_trees(int n){ if(n <= 1) return 1; int i; int sum = 0; int left = 0; int right = 0; for(i=1; i<=n; i++){ left = number_of_trees(i-1); right = number_of_trees(n-i); sum= sum + (left * right); } return sum; } int main(){ printf("\n%d", number_of_trees(3)); return 0; }

Notice that , some of the subproblems are being solved again and again during calculation. What is the method to use when we want to avoid solving subproblems again which are already solved? Yes, dynamic programming.

From formula to calculate catalan number, condition is quite evident

Trees[i] = summation (j = 0 to i) of Tress[j] * Trees[i-j-1] Tress[0] = Trees[1] =1

**Number of binary search trees with N nodes: dynamic programming approach**

#include <stdio.h> int number_of_trees(int n) { int i, j; // Table to store results of subproblems int Trees[n+1]; // Initialize first two values in table Trees[0] = Trees[1] = 1; for (i=2; i<=n; i++) { Trees[i] = 0; for (j=0; j<i; j++) Trees[i] += Trees[j] * Trees[i-j-1]; } return Trees[n]; } int main(void) { printf("\n No. of trees: %d", number_of_trees(3)); return 0; }

Complexity of code to *find number of trees which can be built using n nodes* will be O(n!).

Please let us know if there is something wrong or missing. We would love to hear from you. Sharing is caring.

Pingback: create binary search tree from inorder and preorder traversal – Algorithms and Me()