# Solving Leetcode Interviews in Seconds with AI: Unique Binary Search Trees II


	# Introduction
	In this blog post, we will explore how to solve the LeetCode problem "95" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like [Chatmagic](https://www.chatmagic.app), we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

	# Problem Statement
	> Given an integer n, return all the structurally unique BST's (binary search trees), which has exactly n nodes of unique values from 1 to n. Return the answer in any order.   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  

	# Explanation
	Here's the solution to generate all structurally unique BSTs for a given number of nodes:

*   **Dynamic Programming (Memoization):** The core idea is to break down the problem into smaller, overlapping subproblems. We build BSTs for smaller ranges of numbers (e.g., 1 to k) and then use those to construct BSTs for larger ranges (e.g., 1 to n). Memoization is crucial for efficiency, as it avoids recomputing the same subproblems.
*   **Recursive Tree Construction:** For each number 'i' in the range 1 to n, we consider 'i' as the root. The left subtree will consist of all possible BSTs formed from the numbers 1 to i-1, and the right subtree will consist of all possible BSTs formed from the numbers i+1 to n. We combine these left and right subtrees to create all possible BSTs with 'i' as the root.
*   **Base Cases:** The base cases for our recursion are when the range is empty (no nodes) or contains only one node. An empty range results in a list containing None, and a single-node range results in a list containing a single-node tree.

*   **Runtime Complexity:** O(Catalan(n)), which is approximately O(4<sup>n</sup> / n<sup>1.5</sup>). Storage Complexity: O(Catalan(n)), due to storing all generated trees.

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

def generateTrees(n: int) -> list[TreeNode | None]:
    """
    Generates all structurally unique BSTs for nodes with values 1 to n.

    Args:
        n: The number of nodes.

    Returns:
        A list of TreeNode objects representing all unique BSTs.
    """

    def generate_trees_recursive(start: int, end: int) -> list[TreeNode | None]:
        """
        Recursive helper function to generate BSTs for a given range.

        Args:
            start: The starting value of the range.
            end: The ending value of the range.

        Returns:
            A list of TreeNode objects representing all unique BSTs for the range.
        """

        if start > end:
            return [None]

        trees = []
        for i in range(start, end + 1):
            left_subtrees = generate_trees_recursive(start, i - 1)
            right_subtrees = generate_trees_recursive(i + 1, end)

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

        return trees

    if n == 0:
        return []
    return generate_trees_recursive(1, n)
	```