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)