Unique Binary Search Trees II

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

The code aims to generate all unique binary search trees (BSTs) with a given number of nodes n. Each of these trees has node values from 1 to n, ensuring all trees are unique BSTs. The implementation leverages C++ and employs the following strategies:

• Define the TreeNode class structure for the nodes of the tree.
• Use a recursive function, computeAllBSTs, which calculates all possible BSTs for a range of values, using dynamic programming with memoization to optimize and prevent redundant calculations.
• The memoization is done using a map (cache), which stores the results of previous computations.

The core function computeAllBSTs checks if the values are in the cache and returns the precomputed trees if they are found. If not, it computes all BSTs by trying each number in the range [low, high] as the root, and recursively computing all possible left and right sub-trees. The newly formed trees from these combinations are then added to the trees which gets cached before being returned.

Finally, the generateTrees function initializes the cache and starts the recursive computation for the range 1 to n, ultimately returning all unique BSTs for the specified node count. This solution ensures efficiency and comprehensiveness in generating BSTs by utilizing memoization and recursion.

class Solution {
    public List<TreeNode> generateAllBST(
        int min,
        int max,
        Map<Pair<Integer, Integer>, List<TreeNode>> cache
    ) {
        List<TreeNode> trees = new ArrayList<>();
        if (min > max) {
            trees.add(null);
            return trees;
        }
        if (cache.containsKey(new Pair<>(min, max))) {
            return cache.get(new Pair<>(min, max));
        }
        for (int rootVal = min; rootVal <= max; ++rootVal) {
            List<TreeNode> leftTrees = generateAllBST(min, rootVal - 1, cache);
            List<TreeNode> rightTrees = generateAllBST(rootVal + 1, max, cache);
    
            for (TreeNode leftSubtree : leftTrees) {
                for (TreeNode rightSubtree : rightTrees) {
                    TreeNode rootNode = new TreeNode(rootVal, leftSubtree, rightSubtree);
                    trees.add(rootNode);
                }
            }
        }
        cache.put(new Pair<>(min, max), trees);
        return trees;
    }
    
    public List<TreeNode> generateBinaryTrees(int n) {
        Map<Pair<Integer, Integer>, List<TreeNode>> cache = new HashMap<>();
        return generateAllBST(1, n, cache);
    }
}

The Java solution for generating all unique binary search trees (BSTs) for a given number of nodes utilizes the concept of recursion and dynamic programming with memoization to optimize the operation. Here is the breakdown of the implemented solution:

• The primary method generateBinaryTrees(int n) initializes a cache (HashMap) and calls the recursive generateAllBST method with the range 1 to n representing the values that nodes in the trees can have.
• generateAllBST is a recursive function that:
  • Takes a min and max to define the current range of the node values for the subtree and a cache to store already computed results for specific ranges to avoid redundant calculations.
  • Checks if the min value exceeds max, which implies that the subtree cannot have any nodes, hence a tree represented by null is added to the list.
  • Fetches from cache if the range (min, max) was previously computed.
  • Iteratively selects each value from min to max as a root value (rootVal) and recursively generates all possible left and right subtrees.
  • For each combination of left and right subtrees, a new tree is formed with the current rootVal as the root. This new tree is added to the list of trees.
  • Finally, before returning the list of generated trees, the result is stored in the cache for future reference.

This method effectively reduces the complexity by avoiding the recomputation of results for the same input ranges through memoization. Each subtree configuration is only computed once and reused making the process efficient, especially for larger values of n.

typedef struct hashmap_entry {
    int lookup_key[2];
    struct TreeNode **item_ptr;
    int entry_size;
    UT_hash_handle handle;
} hashmap_entry;
    
void add_to_map(hashmap_entry **map_head, int new_key1, int new_key2, struct TreeNode **node_array, int node_count) {
    hashmap_entry *element;
    element = malloc(sizeof(hashmap_entry));
    element->lookup_key[0] = new_key1;
    element->lookup_key[1] = new_key2;
    element->item_ptr = node_array;
    element->entry_size = node_count;
    HASH_ADD(handle, *map_head, lookup_key, sizeof(int) * 2, element);
}
    
hashmap_entry *search_map(hashmap_entry **map_head, int search_key1, int search_key2) {
    if (*map_head == NULL) return NULL;
    hashmap_entry *element;
    int target_keys[2] = {search_key1, search_key2};
    HASH_FIND(handle, *map_head, target_keys, sizeof(int) * 2, element);
    return element;
}
    
struct TreeNode **generate_BST_subtrees(int first, int last, hashmap_entry **memoization, int *node_count) {
    struct TreeNode **result = (struct TreeNode **)malloc(sizeof(struct TreeNode *) * 5000);
    int tree_count = 0;
    if (first > last) {
        result[tree_count] = NULL;
        *node_count = tree_count + 1;
        return result;
    }
    hashmap_entry *memoized_entry = search_map(memoization, first, last);
    if (memoized_entry) {
        *node_count = memoized_entry->entry_size;
        return memoized_entry->item_ptr;
    }
    for (int mid = first; mid <= last; ++mid) {
        int left_size, right_size;
        struct TreeNode **left_trees = generate_BST_subtrees(first, mid - 1, memoization, &left_size);
        struct TreeNode **right_trees = generate_BST_subtrees(mid + 1, last, memoization, &right_size);
        for (int l_index = 0; l_index < left_size; l_index++) {
            for (int r_index = 0; r_index < right_size; r_index++) {
                struct TreeNode *new_node = (struct TreeNode *)malloc(sizeof(struct TreeNode));
                new_node->val = mid;
                new_node->left = left_trees[l_index];
                new_node->right = right_trees[r_index];
                result[tree_count++] = new_node;
            }
        }
    }
    add_to_map(memoization, first, last, result, tree_count);
    *node_count = tree_count;
    return result;
}
    
struct TreeNode **generateBSTs(int total_nodes, int *total_tree_count) {
    hashmap_entry *memo_root = NULL;
    return generate_BST_subtrees(1, total_nodes, &memo_root, total_tree_count);
}

The given C code offers a solution to generate all unique binary search trees (BSTs) for a given number of nodes using dynamic programming and memoization techniques. Below is a concise explanation of how the program works and the important functions within:

• First, the program defines a hashmap_entry structure to cache the results of subproblems. This structure uses two keys for lookup and stores an array of TreeNode pointers along with the size of this array.

• The add_to_map function adds a new entry to the memoization map. It stores the array of node pointers (TreeNode **) and the count of these nodes, which represent different BST structures for a given range of node values.

• The search_map function searches the memoization map for a previously computed result using two keys representing the range of node values. If found, it returns the cached array of TreeNode pointers, which avoids recalculating the BSTs for that specific range.

• In the generate_BST_subtrees function:

  • This function is designed to generate and return an array of TreeNode pointers. Each TreeNode pointer in the array represents a unique BST.
  • It applies divide-and-conquer by selecting each number as the root and recursively generating all possible left and right subtrees.
  • Combines left and right subtrees in all possible ways to form the BSTs with the current number root.
  • The results, along with their count, are stored in the memoization map to prevent redundant calculations.

• The generateBSTs function initializes the memoization and starts the tree generation process by calling generate_BST_subtrees.

• The recursive process in generating BSTs for each number ensures all configurations are explored and the use of memoization significantly improves the efficiency by storing the results of already computed ranges. This approach ensures that each subtree configuration is generated only once.

Overall, this efficient implementation allows for generating all unique BST configurations for a provided number of nodes using key concepts of recursion, memoization, and combinatorial construction of trees.

var generateAllBSTs = function (low, high, cache) {
    let trees = [];
    if (low > high) {
        trees.push(null);
        return trees;
    }
    let cacheKey = low + "," + high;
    if (cache[cacheKey] !== undefined) {
        return cache[cacheKey];
    }
    for (let num = low; num <= high; ++num) {
        let leftTrees = generateAllBSTs(low, num - 1, cache);
        let rightTrees = generateAllBSTs(num + 1, high, cache);
        for (let leftIndex = 0; leftIndex < leftTrees.length; leftIndex++) {
            for (let rightIndex = 0; rightIndex < rightTrees.length; rightIndex++) {
                let newNode = new TreeNode(num, leftTrees[leftIndex], rightTrees[rightIndex]);
                trees.push(newNode);
            }
        }
    }
    cache[cacheKey] = trees;
    return trees;
};
var generateUniqueTrees = function (totalNodes) {
    let cache = {};
    return generateAllBSTs(1, totalNodes, cache);
};

The given JavaScript solution focuses on generating all possible unique binary search trees (BSTs) that can be created with 'n' distinct nodes, where each node contains a unique integer from 1 to 'n'. This approach utilizes dynamic programming and memoization to efficiently generate trees without redundant calculations.

Understanding the Implementation:

• The generateAllBSTs function:

  • This function is the core that recursively generates all possible BSTs for numbers between low and high.
  • It uses a cache to save previously computed results for specific ranges, improving efficiency by avoiding repetitive calculations.
  • Base Case: If low is greater than high, the function returns an array containing null, indicating the absence of nodes.
  • Recursive Case: The function iterates through each number in the current range, using it as the root, and recursively generates all left and right subtrees by splitting the range. New trees are formed by combining each pair of left and right subtrees with the current root.

• The generateUniqueTrees function:

  • This serves as an initializer and entry point for generating trees with n nodes. It sets up a cache and calls generateAllBSTs with low set to 1 and high set to totalNodes.

Key Points:

• Memoization: A cache object is used to remember the results of subtree formations based on their low and high boundaries, dramatically reducing the number of recursive calls needed.
• Combination: Each number in the range is treated as a potential root, and the combinations of possible left and right subtrees are explored to construct new trees.

This solution efficiently addresses the problem of generating all unique BSTs for a given number of nodes by employing recursive decomposition of the problem combined with caching for performance optimization. Moreover, the recursive nature helps in constructing trees from the bottom up, applying each number as the root and building the corresponding subtree combinations around it.

class Solution:
    def generateBST(self, low, high, cache):
        trees = []
        if low > high:
            trees.append(None)
            return trees
        if (low, high) in cache:
            return cache[(low, high)]
    
        # Construct trees for each possible root from low to high
        for root_val in range(low, high + 1):
            left_trees = self.generateBST(low, root_val - 1, cache)
            right_trees = self.generateBST(root_val + 1, high, cache)
    
            # Connect left and right sub-trees to the current root
            for l_tree in left_trees:
                for r_tree in right_trees:
                    node = TreeNode(root_val, l_tree, r_tree)
                    trees.append(node)
    
        cache[(low, high)] = trees
        return trees
    
    def generateTrees(self, n: int) -> List[Optional[TreeNode]]:
        if n == 0:
            return []
        return self.generateBST(1, n, {})

The Python code provided introduces a solution to dynamically generate all possible unique binary search trees (BSTs) for a given number of nodes, n. The implementation utilizes recursive backtracking adorned with memoization to enhance performance by avoiding repeated calculations. Here's a breakdown of how the solution operates:

• Recursive Tree Construction:

  • The generateBST function is the core method that builds all possible BSTs for node values ranging from low to high. It uses a cache to store previously computed results for specific (low, high) pairs, preventing redundant re-calculations.
  • If low > high, it indicates the completion of a branch, and None is appended to denote an empty subtree.
  • Each number within the low to high interval is considered as a potential root. The function recursively finds all left and right subtrees that can be formed using elements below and above the current root's value, respectively.

• Connecting Sub-trees:

  • The code explores all combinations of left and right subtrees and connects them to the current root value, thus constructing unique BST configurations for each root setting.
  • Each combination of left and right subtree with the root forms a unique BST, which is then collected into the trees list.

• Caching for Efficiency:

  • A dictionary cache is maintained to store the results of previous tree constructions. Before the trees are built for any (low, high) pair, the cache is checked. If the result is already computed, it is returned directly, significantly reducing the number of computations especially in larger trees.

• Public Interface:

  • The generateTrees function provides a public interface and initializes the process. If n is 0, indicating no nodes, it returns an empty list. Otherwise, it calls the generateBST function with values from 1 to n.

This approach effectively leverages dynamic programming principles through memoization and recursive decomposition, allowing it to efficiently solve the problem by constructing each subtree only once and reusing results. By systematically exploring all potential roots and their associated left and right subtrees, the implementation ensures that all unique BSTs are generated and returned.