sundeepblue
4/30/2014 - 7:10 PM

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

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


vector<treenode*> generate_unique_trees(int n) {
    vector<treenode*> res;
    dfs(res, 1, n);
    return res;
}

void dfs(vector<treenode*> &res, int low, int high) {
    if(low > high) {
        res.push_back(NULL);
        return;
    }
    for(int i=low; i<high; i++) {
        vector<treenode*> left_trees, right_trees;
        dfs(left_trees, low, i-1);
        dfs(right_trees, i+1, high);
        // POS1
        for(int j=0; j<left_trees.size(); j++) {
            for(int k=0; k<right_trees.size(); k++) {
                treenode *root = new treenode(i);   // gist, should be here, not at POS1
                root->left = left_trees[j];
                root->right = right_trees[k];
                res.push_back(root);
            }
        }
    }
}