Unique Binary Search Trees II

Problem Statement

In this challenge, we are given a positive integer n and are required to compute all distinct Binary Search Trees (BSTs) that can be formed using exactly n distinct nodes. Each node has a unique value from 1 to n. It's important to create all possible structural configurations of these trees, ensuring they all conform to the properties of a BST, where the left subtree of a node contains only nodes with keys lesser than the node's key and the right subtree only nodes with keys greater.

Our goal as highlighted by the prompt is not merely to count these trees but rather return them in any structure that showcases their formation.

Examples

Example 1

Input:

n = 3

Output:

[[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3,2,null,1]]

Example 2

Input:

n = 1

Output:

[[1]]

Constraints

• 1 <= n <= 8

Approach and Intuition

Understanding the approach to generating all unique BSTs involves both comprehension of the properties of BSTs and the use of recursive tree construction:

Example 1 (n = 3)

1. For n = 3, the trees can have root values ranging from 1 to 3.
2. For each possible root value:
   • Split the remaining values into potential left and right subtrees.
   • Recurse to create all possible left and right subtree combinations.
   • Combine each pair of left and right subtrees with the root to create unique trees.
3. Specifically:
   • If 1 is the root, valid BSTs are formed by combining tree structures developed recursively from values 2 and 3.
   • If 2 is the root, we look into combinatory structures from 1 for left subtree, and 3 for right.
   • If 3 is the root, the recursive formulation looks into trees produced from 1 and 2.

For each root choice, we need to garner all configurations of left and right subtrees, leading to multiple combinations, resulting in BST configurations like [1,null,2,null,3] and [3,1,null,null,2] among others.

Example 2 (n = 1)

1. With n = 1, there is only one possible value and hence one possible tree: [[1]].

Steps to Formulate Trees Recursively

1. Create a function that takes the current range of node values as inputs.
2. If the range is empty or invalid, return a list with one element: None (indicating no subtree).
3. Loop through each number in the range, making it the tree root.
4. Recursively calculate the possible left and right subtrees.
5. For every combination of left and right subtree, form a tree and add it to the list of all possible trees.
6. Return this list upwards in the recursive chain.

Subtleties in Construction

• Recursivity and the selection of each node as a potential root are pivotal, enabling the examination of every possible BST configuration.
• Optimization isn't the primary concern given 1 <= n <= 8, so a combinatorial exploration is feasible.

Essentially, by understanding how trees can split and form based on root selection, and utilizing recursion efficiently, we can generate all possible BST configurations from 1 to n, adhering to the constraints and characteristics of BSTs.

Solutions

class Solution {
public:
    vector<TreeNode*> computeAllBSTs(
        int low, int high, map<pair<int, int>, vector<TreeNode*>>& cache) {
        vector<TreeNode*> trees;
        if (low > high) {
            trees.push_back(nullptr);
            return trees;
        }
        if (cache.find(make_pair(low, high)) != cache.end()) {
            return cache[make_pair(low, high)];
        }
        for (int root = low; root <= high; ++root) {
            vector<TreeNode*> leftTrees = computeAllBSTs(low, root - 1, cache);
            vector<TreeNode*> rightTrees = computeAllBSTs(root + 1, high, cache);
    
            for (auto lTree : leftTrees) {
                for (auto rTree : rightTrees) {
                    TreeNode* rootNode = new TreeNode(root, lTree, rTree);
                    trees.push_back(rootNode);
                }
            }
        }
        return cache[make_pair(low, high)] = trees;
    }
    
    vector<TreeNode*> generateTrees(int n) {
        map<pair<int, int>, vector<TreeNode*>> cache;
        return computeAllBSTs(1, n, cache);
    }
};