Develop all possible Binary Search Trees with key values 1 to N in C++

By G Ganga Jathin

Given the value of N (No of nodes), we try to construct all possible Binary Search Trees using Recursion in C++ Programming Language.

This Packet is based on Developing the code for constructing all possible Binary  Search Trees (BST's) given the value of N (no of nodes)

The main principle code of this problem is that we use recursion to generate all possible configurations of nodes which are BST's.
The relevant code for that which is used is:- 

for (int i = start; i <= end; i++)
  {
    vector leftSubtree = Trees(start, i - 1);

    vector rightSubtree = Trees(i + 1, end);
    for (int j = 0; j < leftSubtree.size(); j++)
    {
      struct Node* left = leftSubtree[j];
      for (int k = 0; k < rightSubtree.size(); k++)
      {
        struct Node * right = rightSubtree[k];
        struct Node * node = newNode(i);// making value i as root
        node->left = left;			 // connect left subtree
        node->right = right;		 // connect right subtree
        list.push_back(node);		 // add this tree to list
      }
    }
  }

Here the initial part of the start and end would be 1 and N(no of nodes) respectively. This continues calls into recursion which when tracked by recursion tree gives all possible configuration of BST's

LeftSubTrees stores all configuration of possible Left Subtrees and similarly for the right which we connect this to the (i) iterable which is supposedly the root node for that subtree and this continues in recursion.



How to use it:- 

1) Open the Zip file
2) Extract the corresponding source file
3)Run the source file in the ide of your choice 
4)Give input of N for the output