95. Unique Binary Search Trees II

Description

The generateTrees function generates all unique binary search trees (BSTs) that store values 1 through n. Each BST is defined such that for any given node, all nodes in the left subtree have values less than the node’s value, and all nodes in the right subtree have values greater. The function returns a list of all possible BST structures that can be formed with these values.

Intuition

The problem can be solved using a recursive approach. The key observation is that for a value k chosen as the root, the left subtree can only consist of values less than k, and the right subtree can only consist of values greater than k. This observation leads to a natural recursive structure: for each possible root value, recursively generate all valid left and right subtrees, then combine them in all possible ways.

Approach

1. Base Case: - If n is 0, return an empty list because no trees can be generated. - If the start index is greater than the end index, return a list containing None, representing an empty tree.
2. Recursive Case: - For each value k from start to end, treat k as the root value. - Recursively generate all left subtrees using values from start to k-1. - Recursively generate all right subtrees using values from k+1 to end. - Combine each left subtree with each right subtree by attaching them to the root node with value k.
3. Memoization: - Use a memoization map to store and reuse results of subproblems to avoid redundant calculations.
4. Return Result: - The final result is a list of all possible BSTs generated by the recursive function.

Complexity

Time Complexity:

The time complexity is exponential in the worst case, approximately (O(4^n / n^{3/2})), which corresponds to the number of unique BSTs that can be generated. This is known as the Catalan number sequence.

Space Complexity:

The space complexity is (O(n \times \text{G(n)})), where (G(n)) is the number of unique BSTs. The space is mainly used by the recursion stack and the memoization map.

Code

C++

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

private:
    std::unordered_map> memo;

    std::vector generateTreesHelper(int start, int end) {
        std::string key = std::to_string(start) + "-" + std::to_string(end);
        if (memo.find(key) != memo.end()) {
            return memo[key];
        }

        std::vector trees;
        if (start > end) {
            trees.push_back(nullptr);
            return trees;
        }

        for (int rootVal = start; rootVal <= end; rootVal++) {
            std::vector leftTrees = generateTreesHelper(start, rootVal - 1);
            std::vector rightTrees = generateTreesHelper(rootVal + 1, end);

            for (auto leftTree : leftTrees) {
                for (auto rightTree : rightTrees) {
                    TreeNode* root = new TreeNode(rootVal);
                    root->left = leftTree;
                    root->right = rightTree;
                    trees.push_back(root);
                }
            }
        }

        memo[key] = trees;
        return trees;
    }
};

Python

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def generateTrees(self, n: int) -> List[TreeNode]:
        if n == 0:
            return []
        return self.generateTreesHelper(1, n)

    def generateTreesHelper(self, start: int, end: int) -> List[TreeNode]:
        memo = {}
        if (start, end) in memo:
            return memo[(start, end)]

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

        for rootVal in range(start, end + 1):
            leftTrees = self.generateTreesHelper(start, rootVal - 1)
            rightTrees = self.generateTreesHelper(rootVal + 1, end)

            for leftTree in leftTrees:
                for rightTree in rightTrees:
                    root = TreeNode(rootVal, leftTree, rightTree)
                    trees.append(root)

        memo[(start, end)] = trees
        return trees

Java

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
        left = null;
        right = null;
    }
}

class Solution {
    private Map> memo = new HashMap<>();

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

    private List generateTreesHelper(int start, int end) {
        String key = start + "-" + end;
        if (memo.containsKey(key)) {
            return memo.get(key);
        }

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

        for (int rootVal = start; rootVal <= end; rootVal++) {
            List leftTrees = generateTreesHelper(start, rootVal - 1);
            List rightTrees = generateTreesHelper(rootVal + 1, end);

            for (TreeNode leftTree : leftTrees) {
                for (TreeNode rightTree : rightTrees) {
                    TreeNode root = new TreeNode(rootVal);
                    root.left = leftTree;
                    root.right = rightTree;
                    trees.add(root);
                }
            }
        }

        memo.put(key, trees);
        return trees;
    }
}

JavaScript

var generateTrees = function (n) {
    if (n === 0) {
        return [];
    }

    const memo = new Map();

    function generateTreesHelper(start, end) {
        if (memo.has(`${start}-${end}`)) {
            return memo.get(`${start}-${end}`);
        }

        const trees = [];
        if (start > end) {
            trees.push(null);
            return trees;
        }

        for (let rootVal = start; rootVal <= end; rootVal++) {
            const leftTrees = generateTreesHelper(start, rootVal - 1);
            const rightTrees = generateTreesHelper(rootVal + 1, end);

            for (const leftTree of leftTrees) {
                for (const rightTree of rightTrees) {
                    const root = new TreeNode(rootVal, leftTree, rightTree);
                    trees.push(root);
                }
            }
        }

        memo.set(`${start}-${end}`, trees);
        return trees;
    }

    return generateTreesHelper(1, n);
};