What's time complexity of algorithm for finding all Unique Binary Search Trees?

Question

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);
                }         
            } 
        }
    }
};

dguan · Accepted Answer · 2014-07-07 19:33:27Z

4

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)).

answered Jul 7, 2014 at 19:33

dguan

1,0331 gold badge9 silver badges21 bronze badges

Sign up to request clarification or add additional context in comments.

6 Comments

Zhaonan Over a year ago

Thank you dguan, description on wikipedia is a little complicated, I need some time to think about it......

dguan Over a year ago

Actually, you could think the problem like this: suppose the number of BSTs for n nodes is C(n), because we are building a BST, for each root node, there could be (0 -- n-1) nodes in left child tree and (n-1 -- 0) nodes in the right, respectively. So the total number of the BSTs C(n) = sum(C(i)*C(n-1-i)), i=0 -- n-1, which is exactly the recursive formula of the Catalan number Catalan(n).

Zhaonan Over a year ago

Catalan(n) = C(n) = sum(C(i)*C(n-1-i)), i=0 -- n-1, since the time complexity = O(C(n)), so the time complexity = O(Catalan(n)). So the next question is how to get Catalan(n), this is the real hard part. Thank you dguan.

dguan Over a year ago

you could get C(n) either by directly using the recursive formula, which is very inefficient; or by using dynamic programming, whose space complexity is O(n) and time complexity is O(n^2), this is much much more efficient.

Zhaonan Over a year ago

Yes dguan, but I need print out all BSTs, so I think I have to use recursion. If I just need the number of Catalan, the DP is a really good choice.

|

Collectives™ on Stack Overflow

What's time complexity of algorithm for finding all Unique Binary Search Trees?

1 Answer 1

6 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

6 Comments

Your Answer

Sign up or log in

Post as a guest

Related