Log inSign up
mediumLeetCodeNot Started

Unique Binary Search Trees

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

BST
Solve on LeetCode
Lesson

Problem Statement

### Problem Statement

Given an integer n, return the number of structurally unique BSTs (binary search trees) which have exactly n nodes of unique values from 1 to n.

---

### Examples

Example 1: ``text Input: n = 3 Output: 5 Explanation: 1 3 3 2 1 \ / / / \ \ 3 2 1 1 3 2 / / \ \ 2 1 2 3

Example 2: ``text Input: n = 1 Output: 1

---

### Constraints - 1 <= n <= 19

Constraints:

  • 1 <= n <= 19

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Understand how the BST ordering invariant decomposes tree construction into independent subproblems.
  • Master the Catalan recurrence relation G(n) = sum_{i=1}^n [G(i-1) * G(n-i)].
  • Implement both O(n2) DP tabulation and O(n) Catalan mathematical evaluation with 64-bit integer overflow protection.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Counting structural variations of trees or valid parentheses
  • Each choice splits the remaining problem into two independent subproblems
  • Symmetric divide-and-conquer where subproblem size depends only on element count

Algorithmic Decision Tree:

  • If counting unique tree structures with n nodes -> Catalan recurrence / 1D DP.
  • If n <= 19 -> Use 1D DP tabulation in O(n2) or iterative Catalan calculation in O(n) with 64-bit integers.

Connected Patterns:

Unique Binary Search Trees IIDifferent Ways to Add ParenthesesClimbing Stairs

1. Recursive Divide and Conquer (Unmemoized)

Intuition

Every value i in 1..n can serve as root. Keys < i go left (i-1 keys), keys > i go right (n-i keys). Sum product across all possible roots.

Algorithm

  1. Define recursive function numTrees(n).
  2. Base cases: if n <= 1, return 1 (empty tree or single node has 1 unique structure).
  3. Initialize total = 0.
  4. Iterate root i from 1 to n: total += numTrees(i - 1) * numTrees(n - i).
  5. Return total.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2
3class Solution {
4public:
5 int numTrees(int n) {
6 if (n <= 1) return 1;
7 int total = 0;
8 for (int i = 1; i <= n; ++i) {
9 total += numTrees(i - 1) * numTrees(n - i);
10 }
11 return total;
12 }
13};
14
15int main() {
16 Solution sol;
17 std::cout << "Recursive n=3: " << sol.numTrees(3) << " (Expected: 5)\n";
18 std::cout << "Recursive n=4: " << sol.numTrees(4) << " (Expected: 14)\n";
19 return 0;
20}

Time & Space Complexity

  • Time complexity: O(3^n)
  • Space complexity: O(n)

2. Dynamic Programming Tabulation (1D DP)

Intuition

Subproblems depend only on node count, not key identities. Tabulate dp[0]..dp[n]. For size i, sum over root j in 1..i: dp[j-1] * dp[i-j].

Algorithm

  1. Create array dp of size n + 1 initialized to 0.
  2. Set base cases: dp[0] = 1, dp[1] = 1.
  3. Loop length i from 2 up to n:
  4. Loop root j from 1 up to i:
  5. dp[i] += dp[j - 1] * dp[i - j];
  6. Return dp[n].
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4class Solution {
5public:
6 int numTrees(int n) {
7 std::vector<int> dp(n + 1, 0);
8 dp[0] = 1;
9 dp[1] = 1;
10 for (int i = 2; i <= n; ++i) {
11 for (int j = 1; j <= i; ++j) {
12 dp[i] += dp[j - 1] * dp[i - j];
13 }
14 }
15 return dp[n];
16 }
17};
18
19int main() {
20 Solution sol;
21 std::cout << "DP n=3: " << sol.numTrees(3) << " (Expected: 5)\n";
22 std::cout << "DP n=5: " << sol.numTrees(5) << " (Expected: 42)\n";
23 return 0;
24}

Time & Space Complexity

  • Time complexity: O(n^2)
  • Space complexity: O(n)

3. Catalan Number Direct Formula

Intuition

The Catalan sequence 1, 1, 2, 5, 14, 42... obeys the closed-form recurrence C(n) = (1/(n+1)) * (2n choose n). Iterative accumulation calculates it in O(n) with 64-bit integer arithmetic.

Algorithm

  1. Initialize 64-bit integer C = 1.
  2. Iterate i from 0 up to n - 1:
  3. C = C * 2 * (2 * i + 1) / (i + 2);
  4. Return (int) C.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2
3class Solution {
4public:
5 int numTrees(int n) {
6 long long C = 1;
7 for (int i = 0; i < n; ++i) {
8 C = C * 2 * (2 * i + 1) / (i + 2);
9 }
10 return static_cast<int>(C);
11 }
12};
13
14int main() {
15 Solution sol;
16 std::cout << "Optimal Catalan n=3: " << sol.numTrees(3) << " (Expected: 5)\n";
17 std::cout << "Optimal Catalan n=5: " << sol.numTrees(5) << " (Expected: 42)\n";
18 std::cout << "Optimal Catalan n=19: " << sol.numTrees(19) << " (Expected: 1767263190)\n";
19 return 0;
20}

Time & Space Complexity

  • Time complexity: O(n)
  • Space complexity: O(1)

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Recursive Divide and ConquerO(3^n)O(n)Pure recursive branching over all roots without caching.Overlapping subproblem recomputation
2.1D DP TabulationO(n^2)O(n)Tabulate dp[0..n] using nested loops.Two nested loops
3.Catalan Direct FormulaOptimalO(n)O(1)Iteratively evaluate the n-th Catalan number via closed recurrence.None

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Setting base case dp[0] = 0 instead of 1, which causes all products dp[j-1] * dp[i-j] to collapse to 0.

Pitfall 2:

Confusing number of unique Binary Trees with Binary Search Trees. General binary trees with n nodes would be Catalan(n) * n! if nodes are labeled.

Pitfall 3:

Dividing before multiplying in Catalan formula, losing precision due to integer truncation.

Crucial Edge Cases to Validate:

  • n = 1 — Base case returns 1 tree (single node root).
  • n = 0 (empty tree) — dp[0] = 1 because an empty tree represents exactly 1 valid configuration (null tree).
  • n = 19 (maximum constraint) — Answer is 1,767,263,190. Intermediate Catalan products exceed 231 - 1, requiring 64-bit integer types.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Always start by drawing n=1, n=2, and n=3 on the whiteboard to demonstrate how choosing each root partitions nodes.
  2. Mention Catalan numbers immediately to showcase deep mathematical fluency, then code the O(n2) DP first before offering the O(n) formula.
  3. State that dp[0] = 1 represents the unique empty tree structure, vital for leaves where one branch has 0 nodes.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why does the number of unique BSTs with keys [1..n] equal the number of BSTs with keys [101..100+n]?

2.What is the recurrence relation for the number of unique BSTs G(n)?

3.Why must 64-bit integers be used when computing the Catalan formula iteratively?

Back to DSA Sheet