Binary Search Trees from keys 1 to n

By | April 24, 2016

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:

1. Initialize a vector list.
2. 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.
3. 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(n2)