What's time complexity of algorithm for finding all Unique Binary Search Trees?
algorithm, big-o, binary-search-tree, c++, recursion
Solution
Given n nodes, the total number of the binary search trees is the Catalan Number, please refer to this link: http://en.wikipedia.org/wiki/Catalan_number. So, the time complexity is also O(Catalan(n)).
Problem
Unique Binary Search Trees 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 ``` Personally I think, time complexity = O(n^n), n is the input. But what's more tight time complexity? C++ ``` /** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ #include <vector> using namespace std; class Solution { public: vector<TreeNode *> generateTrees(int n) { vector<TreeNode *> list; // Input validation. if (n <= 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<TreeNode *> &list) { // Base case. if (left > right) { list.push_back(NULL); return; } for (int i = left; i <= right; i ++) { vector<TreeNode *> left_trees; generateTrees(left, i - 1, left_trees); vector<TreeNode *> right_trees; generateTrees(i + 1, right, right_trees); for (vector<TreeNode *>::iterator left_it = left_trees.begin(); left_it != left_trees.end(); left_it ++) { TreeNode *leftTree = *left_it; for (vector<TreeNode *>::iterator right_it = right_trees.begin(); right_it != right_trees.end(); right_it ++) { TreeNode *rightTree = *right_it; TreeNode *root = new TreeNode(i); root->left = leftTree; root->right = rightTree; list.push_back(root); } } } } }; ```