Unique Binary Search Trees solution and explanation
Google
9 more videos on this problem
Unique Binary Search Trees - Leetcode 96 - Python Dynamic ProgrammingNeetCode · 11:20 · 94K views
Unique Binary Search Trees | Count all structurally unique BSTs | Catalan number | Leetcode #96Techdose · 7:16 · 57K views
Count Unique Binary Search Trees | LeetCode 96 | C++, Java, Python | Catalan NumberKnowledge Center · 16:15 · 9K views
Leetcode - Unique Binary Search Trees (Python)Timothy H Chang · 9:43 · 3K views
[Java] Leetcode 96. Unique Binary Search Tree [DP Distinct Ways #9]Eric Programming · 12:26 · 2K views
unique binary search trees | unique binary search trees leetcode | leetcode 96 | recursive | top dowNaresh Gupta · 11:29 · 2K views
Dp on Trees | Unique Binary Search Trees | Leetcode 96 | Live coding session🔥 | Dynamic ProgrammingCoding Decoded · 11:24 · 1K views
Unique Binary Search Trees | Dynamic Programming | Java | LeetCode - Medium - 96 | The Code MateThe Code Mate · 11:21 · 1K views
LeetCode 96. Unique Binary Search TreesHappy Coding · 19:17 · 1K views
Leetcode Unique Binary Search Trees Java SolutionHackerHeap · 9:37 · 1K views
The problem
Given an integer n, return the number of structurally unique BST's (binary search trees) which has exactly n nodes of unique values from 1 to n.
Example 1:
Input: n = 3 Output: 5
Example 2:
Input: n = 1 Output: 1
Constraints:
1 <= n <= 19
Approach overview
Problem Overview: Given an integer n, count how many structurally unique binary search trees can be built using values from 1 to n. Each number must appear exactly once. Different tree shapes count as different BSTs even if they contain the same values.
Approach 1: Dynamic Programming (Time: O(n2), Space: O(n))
The key observation comes from the BST property: when you pick a value i as the root, all numbers 1..i-1 must form the left subtree and i+1..n must form the right subtree. The number of unique BSTs with i as root equals the number of possible left subtrees multiplied by the number of right subtrees. Define dp[k] as the number of BSTs that can be formed using k nodes. For each total node count k, iterate every node as root and accumulate dp[left] * dp[right]. This bottom-up dynamic programming approach builds answers from smaller subtree sizes.
Initialize dp[0] = 1 and dp[1] = 1 because an empty tree and a single-node tree both have exactly one valid structure. For each nodes from 2 to n, iterate possible roots and compute subtree combinations. The nested iteration leads to O(n2) time complexity. Space stays O(n) for the DP array.
Approach 2: Catalan Number Formula (Time: O(n), Space: O(1))
This problem is a direct application of the Catalan sequence, a classic result from math and combinatorics. The number of unique BSTs with n nodes equals the nth Catalan number. The closed-form formula is C(n) = (1 / (n + 1)) * binomial(2n, n). Instead of computing large factorials, you can iteratively calculate the binomial coefficient using multiplication and division to avoid overflow.
The Catalan interpretation works because every BST can be uniquely defined by choosing a root and recursively combining valid left and right subtree counts. This is exactly the recurrence used in the DP solution, but the mathematical formula collapses the recurrence into a direct computation. The iterative Catalan computation runs in O(n) time with constant extra space.
Recommended for interviews: Start with the Dynamic Programming approach. It demonstrates understanding of the BST root-partition idea and shows you can translate a recursive counting problem into a DP recurrence. Interviewers usually expect dp[n] = sum(dp[left] * dp[right]). Mentioning the Catalan number formula afterward signals deeper algorithm knowledge and familiarity with common combinatorial patterns.
Approach 1: Dynamic Programming
The problem can be efficiently solved using Dynamic Programming. We notice that the number of unique BSTs can be determined as follows: for each node i from 1 to n, calculate the number of left and right subtrees which can form by considering i as the root. We can store these results in a table to avoid redundant work. The relationship can be expressed as:
G(n) = \sum_{i=1}^{n} (G(i-1) * G(n-i))where G(0) = 1 and G(1) = 1 are base cases.
class UniqueBST:
def numTrees(self, n: int) -> int:
dp = [0] * (n + 1)
dp[0], dp[1] = 1, 1
for i in range(2, n + 1):
for j in range(1, i + 1):
dp[i] += dp[j - 1] * dp[i - j]
return dp[n]
if __name__ == "__main__":
solution = UniqueBST()
print(solution.numTrees(3)) # Output: 5public class UniqueBST {
public int numTrees(int n) {
int[] dp = new int[n + 1];
dp[0] = dp[1] = 1;
for (int i = 2; i <= n; i++) {
for (int j = 1; j <= i; j++) {
dp[i] += dp[j - 1] * dp[i - j];
}
}
return dp[n];
}
public static void main(String[] args) {
UniqueBST solution = new UniqueBST();
int n = 3;
System.out.println(solution.numTrees(n)); // Output: 5
}
}#include <vector>
using namespace std;
int numTrees(int n) {
vector<int> dp(n + 1, 0);
dp[0] = dp[1] = 1;
for (int i = 2; i <= n; ++i) {
for (int j = 1; j <= i; ++j) {
dp[i] += dp[j - 1] * dp[i - j];
}
}
return dp[n];
}
int main() {
int n = 3;
int result = numTrees(n);
// Output: 5
return 0;
}function numTrees(n) {
const dp = new Array(n + 1).fill(0);
dp[0] = dp[1] = 1;
for (let i = 2; i <= n; i++) {
for (let j = 1; j <= i; j++) {
dp[i] += dp[j - 1] * dp[i - j];
}
}
return dp[n];
}
const n = 3;
console.log(numTrees(n)); // Output: 5#include <stdio.h>
int numTrees(int n) {
int dp[n + 1];
dp[0] = dp[1] = 1;
for (int i = 2; i <= n; i++) {
dp[i] = 0;
for (int j = 1; j <= i; j++) {
dp[i] += dp[j - 1] * dp[i - j];
}
}
return dp[n];
}
int main() {
int n = 3;
printf("%d\n", numTrees(n)); // Output: 5
return 0;
}using System;
public class UniqueBST {
public int NumTrees(int n) {
int[] dp = new int[n + 1];
dp[0] = dp[1] = 1;
for (int i = 2; i <= n; i++) {
for (int j = 1; j <= i; j++) {
dp[i] += dp[j - 1] * dp[i - j];
}
}
return dp[n];
}
public static void Main(string[] args) {
UniqueBST solution = new UniqueBST();
int n = 3;
Console.WriteLine(solution.NumTrees(n)); // Output: 5
}
}This Python solution utilizes a dynamic programming list to cache the results of subproblems. Starting from initialized base cases, it fills up to n by considering various possibilities of splitting nodes into left and right subtrees.
Time Complexity: O(n^2)
Space Complexity: O(n)
Approach 2: Catalan Number Formula
Using the Catalan number formula provides a mathematical way to solve the problem directly without iteration for up to moderate n. The nth catalan number C(n) is given by:
C(n) = \frac{1}{n+1}\binom{2n}{n}The C(n) represents the number of unique BSTs for n nodes. This can be computed efficiently using mathematical operations.
import math
class UniqueBSTCatalan:
def numTrees(self, n: int) -> int:
return math.comb(2 * n, n) // (n + 1)
if __name__ == "__main__":
solution = UniqueBSTCatalan()
print(solution.numTrees(3)) # Output: 5public class UniqueBSTCatalan {
public long binomialCoeff(int n, int k) {
long res = 1;
if (k > n - k) k = n - k;
for (int i = 0; i < k; ++i) {
res *= (n - i);
res /= (i + 1);
}
return res;
}
public int numTrees(int n) {
long c = binomialCoeff(2 * n, n);
return (int)(c / (n + 1));
}
public static void main(String[] args) {
UniqueBSTCatalan solution = new UniqueBSTCatalan();
int n = 3;
System.out.println(solution.numTrees(n)); // Output: 5
}
}#include <iostream>
using namespace std;
long long binomialCoeff(int n, int k) {
long long res = 1;
if (k > n - k)
k = n - k;
for (int i = 0; i < k; ++i) {
res *= (n - i);
res /= (i + 1);
}
return res;
}
int numTrees(int n) {
long long c = binomialCoeff(2 * n, n);
return (int)(c / (n + 1));
}
int main() {
int n = 3;
cout << numTrees(n) << endl; // Output: 5
return 0;
}function numTrees(n) {
let res = 1;
for (let i = 0; i < n; ++i) {
res = res * (2 * n - i) / (i + 1);
}
return res / (n + 1);
}
const n = 3;
console.log(numTrees(n)); // Output: 5#include <stdio.h>
long long binomialCoeff(int n, int k) {
long long res = 1;
if (k > n - k)
k = n - k;
for (int i = 0; i < k; ++i) {
res *= (n - i);
res /= (i + 1);
}
return res;
}
int numTrees(int n) {
long long c = binomialCoeff(2 * n, n);
return (int)(c / (n + 1));
}
int main() {
int n = 3;
printf("%d\n", numTrees(n)); // Output: 5
return 0;
}using System;
public class UniqueBSTCatalan {
public long BinomialCoeff(int n, int k) {
long res = 1;
if (k > n - k) k = n - k;
for (int i = 0; i < k; ++i) {
res *= (n - i);
res /= (i + 1);
}
return res;
}
public int NumTrees(int n) {
long c = BinomialCoeff(2 * n, n);
return (int)(c / (n + 1));
}
public static void Main(string[] args) {
UniqueBSTCatalan solution = new UniqueBSTCatalan();
int n = 3;
Console.WriteLine(solution.NumTrees(n)); // Output: 5
}
}Python simplification using the built-in math.comb function efficiently computes the Catalan number directly from binomial coefficient calculations. This provides a concise way to achieve the solution.
Time Complexity: O(1)
Space Complexity: O(1)
Approach 3: Dynamic Programming
We define f[i] to represent the number of binary search trees that can be generated from [1, i]. Initially, f[0] = 1, and the answer is f[n].
We can enumerate the number of nodes i, then the number of nodes in the left subtree j \in [0, i - 1], and the number of nodes in the right subtree k = i - j - 1. The number of combinations of the number of nodes in the left subtree and the right subtree is f[j] times f[k], so f[i] = sum_{j = 0}^{i - 1} f[j] times f[i - j - 1].
Finally, return f[n].
The time complexity is O(n), and the space complexity is O(n). Here, n is the number of nodes.
function numTrees(n: number): number {
const f: number[] = Array(n + 1).fill(0);
f[0] = 1;
for (let i = 1; i <= n; ++i) {
for (let j = 0; j < i; ++j) {
f[i] += f[j] * f[i - j - 1];
}
}
return f[n];
}func numTrees(n int) int {
f := make([]int, n+1)
f[0] = 1
for i := 1; i <= n; i++ {
for j := 0; j < i; j++ {
f[i] += f[j] * f[i-j-1]
}
}
return f[n]
}impl Solution {
pub fn num_trees(n: i32) -> i32 {
let n = n as usize;
let mut f = vec![0; n + 1];
f[0] = 1;
for i in 1..=n {
for j in 0..i {
f[i] += f[j] * f[i - j - 1];
}
}
f[n] as i32
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Dynamic Programming | Time Complexity: O(n^2) |
| Catalan Number Formula | Time Complexity: O(1) |
| Dynamic Programming | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming | O(n^2) | O(n) | Best interview explanation; shows BST root partition and DP recurrence clearly |
| Catalan Number Formula | O(n) | O(1) | When you recognize the Catalan pattern and want a mathematically optimized solution |
Frequently asked questions
Is Unique Binary Search Trees easy or hard?
Unique Binary Search Trees is rated Medium difficulty on LeetCode with an acceptance rate around 63%. The challenge is recognizing the recursive subtree counting pattern and converting it into a dynamic programming recurrence.
Unique Binary Search Trees Python/Java solution
In Python or Java, the typical solution builds a DP array where dp[i] stores the number of BSTs using i nodes. For each i from 2 to n, iterate root from 1..i and accumulate dp[root-1] * dp[i-root]. Both languages implement this in O(n^2) time and O(n) space.
How to solve Unique Binary Search Trees in O(n)?
Use the Catalan number formula C(n) = (1 / (n + 1)) * binomial(2n, n). Instead of computing factorials, iteratively calculate the binomial coefficient to avoid overflow. This computes the result in O(n) time and constant space.
What is the best approach for Unique Binary Search Trees?
Dynamic Programming is the most commonly used approach in interviews. Define dp[n] as the number of unique BSTs that can be formed with n nodes and compute dp[n] = sum(dp[left] * dp[right]) for all possible roots. This runs in O(n^2) time and O(n) space and clearly demonstrates the BST root partition idea.
Is Unique Binary Search Trees asked at Google/Amazon/Meta?
Unique Binary Search Trees is a classic dynamic programming and combinatorics problem frequently asked in interviews at companies like Amazon, Google, and Meta. It tests understanding of BST properties, recursion-to-DP transitions, and recognition of Catalan number patterns.
What data structure is used in Unique Binary Search Trees?
The problem revolves around Binary Search Trees conceptually, but the implementation mainly uses a dynamic programming array to store counts of subtree combinations. The DP table captures how many BST structures can be formed for each subtree size.
What is the time complexity of Unique Binary Search Trees?
The standard dynamic programming solution runs in O(n^2) time because for each node count you iterate over all possible roots. Space complexity is O(n) for the DP array. Using the Catalan number formula reduces the computation to O(n) time with O(1) extra space.