# Construct Binary Search Trees from keys 1 to n

### Problem statement to construct a Binary Search Tree(BST) from keys 1 to n.

We are given a list of consecutive numbers from 1 to . Determine the number of binary trees that can be constructed from these numbers.

### Example for building a Binary Search Tree from keys 1 to n:

Input: 1,2,3

Output: 3 3 1 1 2 / \ \ / / \ 2 2 3 2 1 3 / \ / \ 1 1 2 3

### Solution to construct the binary search trees from consecutive keys:

Nodes in the left subtree are smaller and right subtree nodes are greater than the root node. Using this rule, we can construct binary search trees.For a root i, left subtree will have nodes 1 to i-1 and can form x different trees while right subtree will have i+1 to n nodes and can form y different trees. So total possible trees = x*y. Also, we can iterate i from 1 to n. Therefore, total number actually comes out to be equal to a CATALAN NUMBER.

### Algorithm to build the binary search trees from consecutive keys:

- Initialize a vector list.
- For an integer i which ranges from 1 to n,

1. Create the root node with root->data = i.

2.Recursively build the left subtree.

3. Recursively build the right subtree. - Iterate for all left subtrees.

1.Iterate for all right subtrees.

### Code in C++ to build a Binary Search Tree (BST) from the keys:

#include <bits/stdc++.h> using namespace std; struct node { int data; node* left; node* right; }; /*Function to create a new node*/ node* newNode(int key) { node* temp = new node; temp->data = key; temp->left = NULL; temp->right = NULL; return temp; } /*Function for preorder traversal of tree*/ void preorder(node *root) { if(!root) return; cout<<root->data<<" "; preorder(root->left); preorder(root->right); } /*Function to construct a tree*/ vector<node*> buildTree(int start, int end) { vector <node*> list; if(start>end) { list.push_back(NULL); return list; } for(int i=start; i<=end; i++) { /*build left subtree*/ vector <node*> leftSubtree = buildTree(start,i-1); /*build right subtree*/ vector <node*> rightSubtree = buildTree(i+1,end); /*connecting left and right subtrees*/ for(int j=0; j<leftSubtree.size();j++) { node* left = leftSubtree[j]; for(int k=0; k<rightSubtree.size();k++) { node* right = rightSubtree[k]; node* root = newNode(i); root->left = left; root->right = right; list.push_back(root); } } } return list; } int main() { vector <node*> totalTrees = buildTree(1,3); /*print preorder traversal of all trees*/ cout<<"Preorder traversal of trees:\n"; for(int i=0; i<totalTrees.size(); i++) { preorder(totalTrees[i]); cout<<endl; } return 0; }

**OUTPUT:**

Preorder traversal of trees: 1 2 3 1 3 2 2 1 3 3 1 2 3 2 1

Time Complexity: **O(n ^{2})**