Unique Binary Search Trees Ii - Leetcode Solution

Problem statement

Given an integer n, generate all structurally unique binary search trees that store values 1 to n.

Example

Input: 3

Output:

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

Each tree is represented as a list of TreeNode objects, where the val attribute represents the integer value stored in the node, and the left and right attributes represent the left and right subtrees, respectively. A null value represents an empty subtree.

Solution

The problem can be solved using recursive methods. For each value val from 1 to n, we can create the root of a binary search tree with that value, and then recursively generate all possible left and right subtrees for that root. We can then combine each possible left and right subtree with the root to generate all possible binary search trees.

To optimize the algorithm, we can use memoization to store the results of previous recursive calls. This will avoid recomputing the same results multiple times.

We can implement the solution using the following steps:

1. Define a recursive function generateTrees(start, end) that generates all structurally unique binary search trees using the range of integer values from start to end.
2. Base case: If start > end, return a list with a single None element.
3. Loop through the integer values from start to end, and for each value val, do the following:
   1. Recursively generate all possible left subtrees with integer values from start to val - 1, and store the result in a variable left.
   2. Recursively generate all possible right subtrees with integer values from val + 1 to end, and store the result in a variable right.
   3. Loop through each possible left subtree in left, and for each left subtree, loop through each possible right subtree in right, and combine them with the root node val to generate a new binary search tree.
   4. Append the list of generated binary search trees to a variable trees.
4. Return the list of generated binary search trees in trees.

Using memoization, we can store the results of previous recursive calls in a dictionary memo, where the key is a tuple (start, end) representing the range of integer values, and the value is the list of generated binary search trees.

The final implementation in Python is given below:

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 []
        memo = {}
        def generateTreesHelper(start, end):
            if start > end:
                return [None]
            if (start, end) in memo:
                return memo[(start, end)]
            trees = []
            for val in range(start, end+1):
                left = generateTreesHelper(start, val-1)
                right = generateTreesHelper(val+1, end)
                for leftSubtree in left:
                    for rightSubtree in right:
                        root = TreeNode(val)
                        root.left = leftSubtree
                        root.right = rightSubtree
                        trees.append(root)
            memo[(start, end)] = trees
            return trees
        return generateTreesHelper(1, n)

Time Complexity

There are n nodes in each tree, and for each node, we need to generate all possible left and right subtrees. Therefore, the time complexity of the algorithm is O(n * Cn), where Cn is the nth Catalan number, which is the number of unique binary search trees that can be formed with n nodes. The recursive function generateTreesHelper is called for each possible range of integer values from 1 to n, and since there are n possible ranges, the space complexity of the algorithm is O(n * Cn).

1