Unique Binary Search Trees II

XXX. Generate Unique Binary Search Trees

Dynamic Programming

Tree

Recursion

Problem Statement:

Given an integer n, generate all structurally unique binary search trees (BSTs) that store values from 1 to n.

Algorithm:

1. Use recursion to generate all possible left and right subtrees for each root value in the range [1, n].
2. For each root value, recursively generate:
   • All left subtrees using values less than the root.
   • All right subtrees using values greater than the root.
3. Combine all left and right subtrees for each root value to form the complete trees.

Complexity:

Time Complexity: Catalan number growth: O(4ⁿ / √n) for generating all trees.
Space Complexity: O(n) for the recursion stack.

Java Implementation:

public class Solution {
    public List generateTrees(int n) {
        if (n == 0) return new ArrayList<>();
        return generateTrees(1, n);
    }

    public List generateTrees(int start, int end) {
        List trees = new ArrayList<>();
        if (start > end) {
            trees.add(null);
            return trees;
        }

        for (int rootValue = start; rootValue <= end; rootValue++) {
            List leftSubTrees = generateTrees(start, rootValue - 1);
            List rightSubTrees = generateTrees(rootValue + 1, end);

            for (TreeNode leftSubTree : leftSubTrees) {
                for (TreeNode rightSubTree : rightSubTrees) {
                    TreeNode root = new TreeNode(rootValue);
                    root.left = leftSubTree;
                    root.right = rightSubTree;
                    trees.add(root);
                }
            }
        }
        return trees;
    }
}
                

Python Implementation:

def generate_trees(n):
    if n == 0:
        return []
    return generate_trees_range(1, n)

def generate_trees_range(start, end):
    trees = []
    if start > end:
        trees.append(None)
        return trees

    for root_value in range(start, end + 1):
        left_subtrees = generate_trees_range(start, root_value - 1)
        right_subtrees = generate_trees_range(root_value + 1, end)

        for left in left_subtrees:
            for right in right_subtrees:
                root = TreeNode(root_value)
                root.left = left
                root.right = right
                trees.append(root)

    return trees
                

C++ Implementation:

#include 
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    vector generateTrees(int n) {
        if (n == 0) return {};
        return generateTrees(1, n);
    }

    vector generateTrees(int start, int end) {
        vector trees;
        if (start > end) {
            trees.push_back(nullptr);
            return trees;
        }

        for (int rootValue = start; rootValue <= end; ++rootValue) {
            vector leftSubTrees = generateTrees(start, rootValue - 1);
            vector rightSubTrees = generateTrees(rootValue + 1, end);

            for (auto left : leftSubTrees) {
                for (auto right : rightSubTrees) {
                    TreeNode* root = new TreeNode(rootValue);
                    root->left = left;
                    root->right = right;
                    trees.push_back(root);
                }
            }
        }
        return trees;
    }
};