Unique binary search trees II

Given n, generate all structurally unique BST’s (binary search trees) that store values 1…n.

For example,
Given n = 3, your program should return all 5 unique BST’s shown below.

 1        3   3  2   1
  \      /  /   / \  \
   3   2  1   1   3   2
 /   /     \               \
2 1        2                3

C++:
01 void genUniqueBST(int start, int end, vector<TreeNode*>& trees)
02 {
03      if(start>end){
04           trees.push_back(NULL);
05           return;
06      }
07      for(int i=start;i<=end;i++){
08          vector<TreeNode*> left_tree;
09          genUniqueBST(start,i1,left_tree);
10          while(!left_tree.empty()){
11              TreeNode* l_tree=left_tree.back();
12              left_tree.pop_back();
13              vector<TreeNode*> right_tree;
14              genUniqueBST(i+1,end,right_tree);
15              while(!right_tree.empty()){
16                  TreeNode* r_tree=right_tree.back();
17                  right_tree.pop_back();
18                  TreeNode* head=new TreeNode(i);
19                  head->left=l_tree;
20                  head->right=r_tree;
21                  trees.push_back(head);
22              }
23           }
24      }
25      return;
26 }
27 
28 vector<TreeNode *> generateTrees(int n) {
29       vector<TreeNode *> result;
30       genUniqueBST(1,n,result);
31       return result;
32 }
Advertisements
This entry was posted in Recursive, Tree. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s