LeetCode 95: Unique Binary Search Trees II

Problem Description

LeetCode Problem 95

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

Difficulty: Medium

Tags: dynamic programming, backtracking, tree, binary search tree, binary tree

Rating: 93.48%

Solution

Here’s my Python solution to this problem:

# Definition for a binary tree node.
# 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]]:
        if n == 0: return []

        def generate_trees(start, end):
            trees = []

            if start > end:
                trees.append(None)
                return trees

            for i in range(start, end+1):
                left_subtrees = generate_trees(start, i-1)
                right_subtrees = generate_trees(i+1, end)

                # Connect left and right subtrees with root i
                for l in left_subtrees:
                    for r in right_subtrees:
                        root = TreeNode(i)
                        root.left = l
                        root.right = r
                        trees.append(root)

            return trees
        
        return generate_trees(1, n)

Understanding the Algorithm

Let’s break down how the algorithm works with n = 3:

1. First Level: We try each number (1, 2, 3) as the root

• When 1 is root: left = [], right = [2,3]
• When 2 is root: left = [1], right = [3]
• When 3 is root: left = [1,2], right = []

2. Recursive Calls: For each subtree range:

• If the range is empty (start > end), return [None]
• Otherwise, generate all possible configurations

3. Combining Subtrees: For each root value:

• Create new TreeNode with current value
• Attach each combination of left and right subtrees

Complexity Analysis

The solution has the following complexity characteristics:

1. Time Complexity: $O(n^3)$

• Number of possible trees is proportional to n-th Catalan number
• For each tree, we need O(n) to construct it
• Total complexity: O(n * Cn) where Cn is the n-th Catalan number

2. Space Complexity: $O(n)$

• The recursion stack can go up to depth n
• Each recursive call stores a constant amount of data

Note: This is an automated analysis and may not capture all edge cases or specific algorithmic optimizations.