How do you solve Unique Binary Search Trees II on LeetCode?

Unique Binary Search Trees II (LeetCode #95) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n²) time complexity and O(n) space complexity. Key insight: Each unique BST can be formed by choosing a root and recursively forming left and right subtrees.

What is the brute force solution for Unique Binary Search Trees II?

The brute force approach for Unique Binary Search Trees II is Brute Force, with O(n²) time complexity and O(1) space complexity. We can generate all possible trees by considering each number as a root and recursively generating left and right subtrees. This approach explores all combinations, leading to potentially many duplicates. The optimal Optimal Solution approach improves this to O(n²).

What are the interview tips for Unique Binary Search Trees II?

Explain your thought process clearly while coding. Consider edge cases like n = 0 or n = 1. Discuss the time and space complexity of your solution.

What are common mistakes when solving Unique Binary Search Trees II?

Not considering the base case of an empty tree. Failing to combine left and right subtree results correctly.

#95

Unique Binary Search Trees II

Medium

Dynamic ProgrammingBacktrackingTreeBinary Search TreeBinary TreeDynamic ProgrammingRecursion

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n²)
Space	O(1)	O(n)

💡

Intuition

Time O(n²)Space O(n)

We can use dynamic programming to build the number of unique BSTs for each count of nodes up to n. This approach avoids redundant calculations by storing results for previously computed values.

⚙️

Algorithm

4 steps

1Step 1: Create an array dp where dp[i] will store the number of unique BSTs that can be formed with i nodes.
2Step 2: Initialize dp[0] = 1 (an empty tree) and dp[1] = 1 (one node tree).
3Step 3: For each count of nodes from 2 to n, calculate dp[i] by considering each node as a root and summing the products of left and right subtree counts.
4Step 4: Use the dp array to construct the unique BSTs recursively.

solution.py30 lines

1class TreeNode:
2    def __init__(self, val=0, left=None, right=None):
3        self.val = val
4        self.left = left
5        self.right = right
6
7def generateTrees(n):
8    if n == 0:
9        return []
10    dp = [0] * (n + 1)
11    dp[0], dp[1] = 1, 1
12    for i in range(2, n + 1):
13        for j in range(1, i + 1):
14            dp[i] += dp[j - 1] * dp[i - j]
15    return generate(1, n)
16
17def generate(start, end):
18    if start > end:
19        return [None]
20    all_trees = []
21    for i in range(start, end + 1):
22        left_trees = generate(start, i - 1)
23        right_trees = generate(i + 1, end)
24        for left in left_trees:
25            for right in right_trees:
26                root = TreeNode(i)
27                root.left = left
28                root.right = right
29                all_trees.append(root)
30    return all_trees

ℹ

Complexity note: The time complexity remains O(n²) due to the nested loops for calculating the number of unique BSTs, but we save space by using the dp array to avoid recalculating results.

1Each unique BST can be formed by choosing a root and recursively forming left and right subtrees.
2Dynamic programming helps to avoid recalculating results for the same subtree configurations.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.