Solution Explanation: Generating Unique Binary Search Trees II

This problem asks to generate all structurally unique Binary Search Trees (BSTs) with n nodes, where each node's value is unique and ranges from 1 to n. The solution uses a Depth-First Search (DFS) approach with backtracking to explore all possibilities.

Approach:

The core idea is to recursively build BSTs. For a given range [i, j] (inclusive), we consider each number v within this range as a potential root. Then:

1. Base Case: If i > j, the range is empty, so we return a list containing null (representing an empty subtree).
2. Recursive Step: If i <= j, we iterate through each v in [i, j]. For each v:
   • We recursively generate all possible left subtrees using dfs(i, v - 1).
   • We recursively generate all possible right subtrees using dfs(v + 1, j).
   • We combine each left subtree with each right subtree, creating a new TreeNode with v as the root.
   • These newly created BSTs are added to the result list.

Finally, the dfs(1, n) call gives us all unique BSTs for the range [1, n].

Time Complexity Analysis:

The time complexity is dominated by the recursive calls in dfs. The number of unique BSTs with n nodes is given by the nth Catalan number, denoted as Cn, which is approximately 4<sup>n</sup> / (n√(πn)). In each recursive call, we iterate through j - i + 1 possible root values. Therefore, the overall time complexity is roughly O(4n / (n√(πn)) * n) which simplifies to O(4n / √n). This is an exponential time complexity.

Space Complexity Analysis:

The space complexity is determined by both the recursion depth (which is O(n) in the worst case) and the size of the resulting list of BSTs. The number of unique BSTs is again given by the nth Catalan number, meaning the space complexity to store all the generated BSTs is O(4n / √n).

Code Explanation (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[Optional[TreeNode]]:
        def dfs(i: int, j: int) -> List[Optional[TreeNode]]:
            if i > j:
                return [None]  # Base case: empty range
            ans = []
            for v in range(i, j + 1): # Iterate through potential root values
                left_trees = dfs(i, v - 1) # Generate left subtrees
                right_trees = dfs(v + 1, j) # Generate right subtrees
                for l in left_trees:
                    for r in right_trees:
                        ans.append(TreeNode(v, l, r)) #Combine and create new tree
            return ans
        return dfs(1, n)

The code in other languages (Java, C++, Go, TypeScript, Rust) follows the same algorithmic structure. The primary differences lie in syntax and data structure implementations (e.g., using ArrayList in Java, vector in C++, slices in Go etc.). The core recursive DFS logic remains the same.