How do you solve Unique Binary Search Trees on LeetCode?

Unique Binary Search Trees (LeetCode #96) 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: The number of unique BSTs can be derived from the structure of smaller trees.

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

The brute force approach for Unique Binary Search Trees is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach involves generating all possible binary search trees (BSTs) for a given number of nodes and counting the unique structures. This is done recursively by selecting each node as the root and calculating the number of unique trees that can be formed with the remaining nodes. The optimal Optimal Solution approach improves this to O(n²).

What are the interview tips for Unique Binary Search Trees?

Explain your thought process clearly before coding. Consider edge cases and base cases upfront. Discuss time and space complexity as you develop your solution.

What are common mistakes when solving Unique Binary Search Trees?

Not recognizing the recursive structure of the problem. Failing to use dynamic programming to optimize the brute-force solution.

#96

Unique Binary Search Trees

Medium

MathDynamic ProgrammingTreeBinary 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)

The optimal solution uses dynamic programming to store the number of unique BSTs for each number of nodes, avoiding redundant calculations. This is based on the Catalan number formula, which counts the unique BSTs efficiently.

⚙️

Algorithm

4 steps

1Step 1: Create an array dp of size n+1 initialized to 0, with dp[0] = 1 (base case).
2Step 2: For each i from 1 to n, calculate dp[i] by considering each j from 1 to i as the root.
3Step 3: For each root j, the number of unique trees is dp[j-1] (left) * dp[i-j] (right). Sum these products to get dp[i].
4Step 4: Return dp[n] as the result.

solution.py7 lines

1def numTrees(n):
2    dp = [0] * (n + 1)
3    dp[0] = 1
4    for i in range(1, n + 1):
5        for j in range(1, i + 1):
6            dp[i] += dp[j - 1] * dp[i - j]
7    return dp[n]

ℹ

Complexity note: The time complexity is O(n²) due to the nested loops, but we save results in dp to avoid recalculating, leading to a linear space complexity.

1The number of unique BSTs can be derived from the structure of smaller trees.
2Dynamic programming helps to avoid redundant calculations.

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