[Medium] 96. Unique Binary Search Trees
[Medium] 96. Unique Binary Search Trees
Given an integer n, return the number of structurally unique BST’s (binary search trees) that have exactly n nodes with values from 1 to n.
Examples
Example 1:
Input: n = 3
Output: 5
Explanation: For n = 3, there are a total of 5 unique BST's:
1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3
Example 2:
Input: n = 1
Output: 1
Constraints
- 1 <= n <= 19
Clarification Questions
Before diving into the solution, here are 5 important clarifications and assumptions to discuss during an interview:
-
BST definition: What is a Binary Search Tree? (Assumption: Tree where left subtree < root < right subtree - BST property)
-
Node values: What values do nodes have? (Assumption: Nodes labeled 1 to n - values from 1 to n)
-
Tree structure: What makes trees “unique”? (Assumption: Different structures - same values but different arrangements count as different trees)
-
Return value: Should we return trees or count? (Assumption: Return count - number of structurally unique BSTs)
-
Empty tree: What if n is 0? (Assumption: Per constraints n >= 1, but typically empty tree counts as 1)
Interview Deduction Process (20 minutes)
Step 1: Brute-Force Approach (5 minutes)
Initial Thought: “I need to count unique BSTs. Let me try generating all possible BSTs and count them.”
Naive Solution: Recursively generate all possible BST structures for n nodes, count distinct structures.
Complexity: O(C(n) × n) time where C(n) is Catalan number, O(C(n) × n) space
Issues:
- Generates all trees which is expensive
- Catalan numbers grow exponentially
- Very inefficient
- Doesn’t leverage optimal substructure
Step 2: Semi-Optimized Approach (7 minutes)
Insight: “This has optimal substructure. Number of BSTs with n nodes depends on root choice and left/right subtree sizes.”
Improved Solution: Use DP. For n nodes, try each node as root. If root is i, left subtree has i-1 nodes, right has n-i nodes. dp[n] = sum(dp[i-1] × dp[n-i]) for i from 1 to n.
Complexity: O(n²) time, O(n) space
Improvements:
- Leverages optimal substructure
- O(n²) time instead of exponential
- Correctly counts all unique BSTs
- Much more efficient
Step 3: Optimized Solution (8 minutes)
Final Optimization: “DP is optimal. Can also use Catalan number formula for direct calculation.”
Best Solution: DP approach is optimal. Can also use Catalan number formula: C(n) = (2n)! / ((n+1)! × n!), but DP is more intuitive and easier to implement.
Complexity: O(n²) time, O(n) space
Key Realizations:
- DP is natural approach - optimal substructure
- O(n²) time is optimal for DP approach
- Catalan numbers give direct formula
- DP is more intuitive than formula
Approach
There are three main approaches to solve this problem:
- Dynamic Programming: Build up the solution using the recurrence relation
- Catalan Numbers: Use the mathematical formula for Catalan numbers
- Optimized DP: Slight variations in DP implementation
The key insight is that the number of unique BSTs follows the Catalan number sequence.
Solution 1: Dynamic Programming (Initialized with 1s)
class Solution {
public:
int numTrees(int n) {
vector<int> cache(n + 1, 1);
for(int i = 2; i <= n; i++) {
int sum = 0;
for(int j = 1; j <= i; j++) {
int left = j - 1;
int right = i - j;
sum += cache[left] * cache[right];
}
cache[i] = sum;
}
return cache[n];
}
};
Time Complexity: O(n²) - Nested loops Space Complexity: O(n) - DP array
Solution 2: Dynamic Programming (Explicit Base Cases)
class Solution {
public:
int numTrees(int n) {
vector<int> cache(n + 1, 0);
cache[0] = 1;
cache[1] = 1;
for(int i = 2; i <= n; i++) {
for(int j = 1; j <= i; j++) {
cache[i] += cache[j - 1] * cache[i - j];
}
}
return cache[n];
}
};
Time Complexity: O(n²) - Nested loops Space Complexity: O(n) - DP array
Solution 3: Catalan Numbers Formula
class Solution {
public:
int numTrees(int n) {
long long rtn = 1;
for(int i = 0; i < n; i++) {
rtn = rtn * 2 * (2 * i + 1) / (i + 2);
}
return (int)rtn;
}
};
Time Complexity: O(n) - Single loop Space Complexity: O(1) - Constant space
Step-by-Step Example (Solution 1)
For n = 3:
- Initial: cache = [1, 1, 1, 1]
- i = 2:
- j = 1: left = 0, right = 1 → cache[0] * cache[1] = 1 * 1 = 1
- j = 2: left = 1, right = 0 → cache[1] * cache[0] = 1 * 1 = 1
- cache[2] = 1 + 1 = 2
- i = 3:
- j = 1: left = 0, right = 2 → cache[0] * cache[2] = 1 * 2 = 2
- j = 2: left = 1, right = 1 → cache[1] * cache[1] = 1 * 1 = 1
- j = 3: left = 2, right = 0 → cache[2] * cache[0] = 2 * 1 = 2
- cache[3] = 2 + 1 + 2 = 5
Final result: 5
Mathematical Insight
The number of unique BSTs with n nodes is the n-th Catalan number:
C(n) = (2n)! / ((n+1)! * n!) = (1/(n+1)) * C(2n,n)
The recurrence relation is: C(n) = Σ(i=1 to n) C(i-1) * C(n-i)
Key Insights
- Recurrence Relation: For each root i, left subtree has i-1 nodes, right subtree has n-i nodes
- Catalan Numbers: The sequence follows Catalan number pattern
- Dynamic Programming: Build up solutions from smaller subproblems
- Mathematical Formula: Direct calculation using Catalan number formula
Solution Comparison
- DP (Solution 1): Initializes all values to 1, simpler logic
- DP (Solution 2): Explicit base cases, more traditional DP approach
- Catalan Formula: Most efficient O(n) time, O(1) space
Common Mistakes
- Not understanding the recurrence relation for BST counting
- Integer overflow in Catalan number calculation
- Incorrect base cases in DP approach
- Confusing with permutation problems instead of combination
Edge Cases
- n = 1: return 1 (single node)
- n = 2: return 2 (two possible BSTs)
- n = 0: return 1 (empty tree)