Loading problems...
TL;DR: The optimal solution uses Dynamic Programming to build the count of unique BSTs by summing the Cartesian product of left and right subtree counts for every possible root node.
The problem asks us to determine the total number of structurally unique Binary Search Trees (BSTs) that can be formed using exactly n nodes with unique values ranging from 1 to n. While the values are distinct, the structural uniqueness depends primarily on the number of nodes available to form the left and right subtrees.
This is a classic combinatorial problem often featured in technical interviews. The LeetCode 96 Solution relies on recognizing that the problem decomposes into identical subproblems based on the count of nodes, fitting perfectly into a Dynamic Programming framework.
A naive approach attempts to solve the problem using simple recursion without storing intermediate results. To count the number of BSTs with n nodes, one might iterate through every number from to , treating as the root. For each root , the function recursively calls itself to calculate the number of unique left subtrees (using nodes) and right subtrees (using nodes).
Pseudo-code:
textfunction count(n): if n <= 1 return 1 total = 0 for i from 1 to n: total += count(i - 1) * count(n - i) return total
Complexity Analysis:
The time complexity of this brute force approach is exponential. Specifically, the recurrence relation describes the Catalan numbers. Without memoization, the algorithm repeatedly solves the same subproblems (e.g., calculating count(2) multiple times for different branches of the recursion tree). For , this would result in a massive number of redundant calculations, leading to a Time Limit Exceeded (TLE) error.
The crucial insight needed to move from brute force to an optimal solution is understanding how a BST is constructed relative to its root.
Therefore, we can define a function as the number of unique BSTs of length . To calculate , we sum over all possible roots :
Here, represents the count of left subtrees (nodes smaller than root ), and represents the count of right subtrees (nodes larger than root ).

Let's trace the algorithm for n = 3.
Initialize DP Array:
dp array of size 4 (indices 0 to 3).
dp[0] = 1, dp[1] = 1.
Calculate dp[2] (Trees with 2 nodes):
dp[0]), Right has 1 node (dp[1]).
Product: .dp[1]), Right has 0 nodes (dp[0]).
Product: .dp[2]: .Calculate dp[3] (Trees with 3 nodes):
dp[0]), Right has 2 nodes (dp[2]).
Product: .dp[1]), Right has 1 node (dp[1]).
Product: .Output: Return dp[3], which is 5.
The correctness relies on the exhaustive partition property of Binary Search Trees. Every BST must have a root. If we group all valid BSTs of size by their root value, we create disjoint sets of trees. The size of the set where is the root is determined strictly by the number of ways to arrange the remaining nodes into the left and right subtrees. Since the choices for the left subtree and right subtree are independent, the Multiplication Principle applies. By summing these products for all possible roots through , we guarantee that every structurally unique BST is counted exactly once.
cppclass Solution { public: int numTrees(int n) { // dp[i] stores the number of unique BSTs with i nodes std::vector<int> dp(n + 1, 0); // Base cases dp[0] = 1; // Empty tree dp[1] = 1; // Single node tree // Build up the solution for lengths 2 to n for (int i = 2; i <= n; ++i) { // Iterate through all possible roots j for a tree of length i for (int j = 1; j <= i; ++j) { // dp[i] += (left subtrees count) * (right subtrees count) // Left subtree has j-1 nodes // Right subtree has i-j nodes dp[i] += dp[j - 1] * dp[i - j]; } } return dp[n]; } };
javaclass Solution { public int numTrees(int n) { // dp[i] stores the number of unique BSTs with i nodes int[] dp = new int[n + 1]; // Base cases dp[0] = 1; // Empty tree dp[1] = 1; // Single node tree // Build up the solution for lengths 2 to n for (int i = 2; i <= n; i++) { // Iterate through all possible roots j for a tree of length i for (int j = 1; j <= i; j++) { // dp[i] += (left subtrees count) * (right subtrees count) // Left subtree has j-1 nodes // Right subtree has i-j nodes dp[i] += dp[j - 1] * dp[i - j]; } } return dp[n]; } }
pythonclass Solution: def numTrees(self, n: int) -> int: # dp[i] stores the number of unique BSTs with i nodes dp = [0] * (n + 1) # Base cases dp[0] = 1 # Empty tree dp[1] = 1 # Single node tree # Build up the solution for lengths 2 to n for i in range(2, n + 1): # Iterate through all possible roots j for a tree of length i for j in range(1, i + 1): # dp[i] += (left subtrees count) * (right subtrees count) # Left subtree has j-1 nodes # Right subtree has i-j nodes dp[i] += dp[j - 1] * dp[i - j] return dp[n]
Time Complexity: We use two nested loops. The outer loop runs from to to fill the DP table. The inner loop runs from to the current , performing constant-time multiplication and addition. The total number of operations is proportional to the sum of integers from to , which is , resulting in quadratic time complexity.
Space Complexity: We require an array of size to store the results of subproblems.
The Dynamic Programming logic used here is directly applicable to other combinatorial problems:
Why do I get the wrong answer for small inputs?
dp[0] = 1.dp[0] is 0, the multiplication dp[j-1] * dp[i-j] will result in 0 whenever a subtree is empty (e.g., node 1 as root has an empty left subtree).Why does my recursive solution Time Limit Exceeded (TLE)?
numTrees(2)) are re-calculated thousands of times for larger .dp[2]), Right has 0 nodes (dp[0]).
Product: .dp[3]: .Can I just use the mathematical formula for Catalan numbers?