title: What's time complexity of algorithm for finding all Unique Binary Search Trees?
body: <blockquote>
    <p><strong>Unique Binary Search Trees</strong> <br>
    Given n,  generate all structurally unique
    BST's (binary search trees) that store values 1...n.</p>
    
    <p><strong>For example</strong>, Given n = 3,  <br>
    your program should return all 5 unique
    BST's shown below. </p>
  
  <pre><code>    1         3         3         2         1 
       \       /         /         / \         \ 
        3     2         1         1   3         2 
       /     /           \                       \ 
      2     1             2                       3
  </code></pre>
    
    <p><hr>
    <strong>Personally I think</strong>,<br> time complexity = O(n^n), n is the input. <br>
    <strong>But what's more tight time complexity?</strong> <hr>
    <strong>C++</strong></p>
  </blockquote>
  
  <pre><code>/**
   * Definition for binary tree
   * struct TreeNode {
   *     int val;
   *     TreeNode *left;
   *     TreeNode *right;
   *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
   * };
   */
  #include &lt;vector&gt;
  using namespace std;
  
  class Solution {
  public:
      vector&lt;TreeNode *&gt; generateTrees(int n) {
          vector&lt;TreeNode *&gt; list;
  
          // Input validation.
          if (n &lt;= 0) {
              list.push_back(NULL);
              return list;
          }
  
          int left = 1;
          int right = n;
          generateTrees(left, right, list);
  
          return list;
      }
  
      void generateTrees(int left, int right, vector&lt;TreeNode *&gt; &amp;list) {
          // Base case.
          if (left &gt; right) {
              list.push_back(NULL);
              return;
          }
  
          for (int i = left; i &lt;= right; i ++) {
              vector&lt;TreeNode *&gt; left_trees;
              generateTrees(left, i - 1, left_trees);
  
              vector&lt;TreeNode *&gt; right_trees;
              generateTrees(i + 1, right, right_trees);
  
              for (vector&lt;TreeNode *&gt;::iterator left_it = left_trees.begin();
                   left_it != left_trees.end(); left_it ++) {
  
                  TreeNode *leftTree = *left_it;
  
                  for (vector&lt;TreeNode *&gt;::iterator right_it = right_trees.begin();
                       right_it != right_trees.end(); right_it ++) {
  
                      TreeNode *rightTree = *right_it;
  
                      TreeNode *root = new TreeNode(i);
                      root-&gt;left = leftTree;
                      root-&gt;right = rightTree;
  
                      list.push_back(root);
                  }         
              } 
          }
      }
  };
  </code></pre>