Unique Binary Search Trees
MedPrompt
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: 5Example 2:
Input: n = 1
Output: 1
Constraints:
1 <= n <= 19
Approaches
3 approaches with complexity analysis and trade-offs.
This approach directly translates the recursive formula G(n) = sum_{i=1 to n} [G(i-1) * G(n-i)] into a recursive function. The function numTrees(n) will calculate the result by iterating from i = 1 to n, choosing i as the root, and recursively calling itself to find the number of unique BSTs for the left subtree (i-1 nodes) and the right subtree (n-i nodes). The sum of these products for all possible roots i gives the final answer.
Algorithm
- Define a function
numTrees(n). - Handle the base cases: if
nis 0 or 1, return 1. - Initialize a variable
totalto 0. - Iterate with a loop from
i = 1ton. In each iteration,irepresents the value of the root node. - For each
i, recursively callnumTrees(i - 1)to get the count of unique left subtrees andnumTrees(n - i)for the right subtrees. - Multiply the results from the recursive calls and add the product to
total. - After the loop, return
total.
Walkthrough
The core idea is to recognize that the number of unique BSTs with n nodes is the sum of possibilities for each node i (from 1 to n) being the root. If we choose i as the root, the i-1 nodes smaller than i will form the left subtree, and the n-i nodes larger than i will form the right subtree. The number of ways to form the left subtree is numTrees(i-1), and the number of ways to form the right subtree is numTrees(n-i). The total number of BSTs with i as the root is the product numTrees(i-1) * numTrees(n-i). We sum this product over all possible roots i from 1 to n. The base cases are numTrees(0) = 1 (one empty tree) and numTrees(1) = 1 (one tree with a single node).
public int numTrees(int n) { if (n <= 1) { return 1; } int count = 0; for (int i = 1; i <= n; i++) { // i is the root int leftTrees = numTrees(i - 1); int rightTrees = numTrees(n - i); count += leftTrees * rightTrees; } return count;}Complexity
Time
O(4^n / n^(3/2))
Space
O(n)
Trade-offs
Pros
Simple to understand and implement directly from the problem's recursive definition.
Cons
Extremely inefficient due to redundant calculations of the same subproblems.
Will likely result in a 'Time Limit Exceeded' error for
ngreater than around 15.
This approach improves upon the recursive solution by using dynamic programming to avoid recomputing the same subproblems. We can use an array, say dp, of size n+1 to store the number of unique BSTs for i nodes, where dp[i] stores G(i). We compute the values of dp from i=0 up to n in a bottom-up fashion.
Algorithm
- Create an integer array
dpof sizen + 1. - Initialize the base cases:
dp[0] = 1anddp[1] = 1. - Iterate with an outer loop from
i = 2ton. This loop calculates the number of unique BSTs forinodes. - Inside the outer loop, use an inner loop from
j = 1toi. This loop considers eachjas the root of the BST withinodes. - In the inner loop, calculate the number of trees with
jas the root:dp[j-1] * dp[i-j]. Add this todp[i]. - After the loops complete,
dp[n]will hold the result fornnodes. Returndp[n].
Walkthrough
The problem has optimal substructure and overlapping subproblems, making it a perfect candidate for dynamic programming. The number of unique BSTs for n nodes, G(n), depends on the values of G(k) for k < n. We can build the solution bottom-up by creating an array dp of size n+1. We initialize dp[0] = 1 and dp[1] = 1. Then, we iterate from i = 2 to n to compute dp[i]. To compute dp[i], we use the same recurrence relation: dp[i] = sum_{j=1 to i} [dp[j-1] * dp[i-j]]. The inner loop iterates through all possible root choices (j from 1 to i) for a tree of size i. For each j, the left subtree has j-1 nodes and the right has i-j nodes. The final answer is dp[n].
public int numTrees(int n) { if (n <= 1) { return 1; } int[] dp = new int[n + 1]; dp[0] = 1; dp[1] = 1; // Calculate dp[i] for i from 2 to n for (int i = 2; i <= n; i++) { // For a tree with i nodes, choose j as the root (1-indexed) for (int j = 1; j <= i; j++) { // Left subtree has j-1 nodes, right has i-j nodes dp[i] += dp[j - 1] * dp[i - j]; } } return dp[n];}Complexity
Time
O(n^2)
Space
O(n)
Trade-offs
Pros
Much more efficient than the recursive approach.
Avoids re-computation and can handle the given constraints (
n <= 19) easily.
Cons
Requires O(n) extra space for the DP array.
The sequence of the number of unique BSTs, G(n), is known as the n-th Catalan number, C_n. Instead of computing it recursively or with DP, we can use the direct mathematical formula for Catalan numbers: C_n = (1 / (n+1)) * (2n choose n). This is the most efficient method.
Algorithm
- Handle the base case: if
n <= 1, return 1. - Recognize the problem as finding the n-th Catalan number,
C_n. - Use the formula
C_n = (1 / (n+1)) * (2n choose n). - Calculate
(2n choose n)iteratively to avoid overflow. Initialize alongvariableresultto 1. - Loop from
i = 0ton-1. In each step, updateresultbyresult = result * (2n - i) / (i + 1). This computes(2n choose n). - After the loop, divide the
resultby(n+1)to get the n-th Catalan number. - Cast the final
longresult tointand return.
Walkthrough
The problem is a classic combinatorial problem whose solution is given by the Catalan numbers. The n-th Catalan number, C_n, is given by the formula C_n = (2n)! / ((n+1)! * n!). A naive implementation might lead to overflow issues with factorials. A better way is to compute (2n choose n) iteratively. We can calculate (2n choose n) as product_{i=1 to n} (n+i)/i. An even better way for implementation is to calculate (2n choose n) as (2n * (2n-1) * ... * (n+1)) / n!. We can compute this term by term to keep the intermediate numbers smaller and avoid overflow by performing multiplication and division in each step. Since n <= 19, a long data type is sufficient to hold the intermediate values.
public int numTrees(int n) { if (n <= 1) { return 1; } // The result is the n-th Catalan number, C_n. // C_n = (1/(n+1)) * C(2n, n) // We calculate C(2n, n) iteratively to avoid overflow. long result = 1; for (int i = 0; i < n; i++) { // C(2n, n) = product_{i=0 to n-1} (2n-i)/(i+1) result = result * (2L * n - i) / (i + 1); } // The loop above calculates C(2n, n). We need C_n. // C_n = C(2n, n) - C(2n, n-1) = C(2n, n) / (n+1) return (int) (result / (n + 1));}Complexity
Time
O(n)
Space
O(1)
Trade-offs
Pros
Most efficient solution in terms of both time and space.
Directly computes the result without recursion or extra storage arrays.
Cons
Requires knowledge of combinatorics and Catalan numbers.
Implementation needs to be careful to avoid integer overflow with large intermediate values, though using
longis sufficient for the given constraints.
Solutions
Solution
public class Solution { public int NumTrees(int n) { int[] f = new int[n + 1]; f[0] = 1; for (int i = 1; i <= n; ++i) { for (int j = 0; j < i; ++j) { f[i] += f[j] * f[i - j - 1]; } } return f[n]; }}public class Unique_Binary_Search_Trees { public static void main ( String [] args ) { Unique_Binary_Search_Trees out = new Unique_Binary_Search_Trees (); Solution s = out . new Solution (); System . out . println ( s . numTrees ( 3 )); } public class Solution { public int numTrees ( int n ) { if ( n <= 0 ) { return 0 ; } // dp[i] represents the number of BST that can be composed of i numbers int [] dp = new int [ n + 1 ]; dp [ 0 ] = 1 ; // null is counted as one unique tree for ( int i = 1 ; i <= n ; i ++) { // 1...n for ( int j = 1 ; j <= i ; j ++) { // for each fixed n, calculate its sum dp [ i ] += dp [ j - 1 ] * dp [ i - j ]; } } return dp [ n ]; } } public class Solution_recursion { public int numTrees ( int n ) { if ( n < 0 ) { return 0 ; } if ( n == 0 || n == 1 ) { return 1 ; } int sum = 0 ; for ( int i = 1 ; i <= n ; i ++) { // 2 conditions: unique && BST. => inorder-visit will generate ordered sequence // so, if decide root, then left and right can be calculated // @note: root is "i", left has "i-1" nodes, right has "n - (i - 1) - 1"=="n - i" nodes sum += numTrees ( i - 1 ) * numTrees ( n - i ); } return sum ; } } } ////// class Solution { public int numTrees ( int n ) { int [] dp = new int [ n + 1 ]; dp [ 0 ] = 1 ; for ( int i = 1 ; i <= n ; ++ i ) { for ( int j = 0 ; j < i ; ++ j ) { dp [ i ] += dp [ j ] * dp [ i - j - 1 ]; } } return dp [ n ]; } }class Solution { public: int numTrees ( int n ) { vector < int > f ( n + 1 ); f [ 0 ] = 1 ; for ( int i = 1 ; i <= n ; ++ i ) { for ( int j = 0 ; j < i ; ++ j ) { f [ i ] += f [ j ] * f [ i - j - 1 ]; } } return f [ n ]; } };class Solution : def numTrees ( self , n : int ) -> int : dp = [ 0 ] * ( n + 1 ) dp [ 0 ] = 1 # e.g, null is counted as one unique tree for i in range ( 1 , n + 1 ): # up to i-1, when j=i-1 meaning left child having i-1 node then i is the root for j in range ( i ): dp [ i ] += dp [ j ] * dp [ i - j - 1 ] # -1, not counting root return dp [ - 1 ] ############ class Solution ( object ): def _numTrees ( self , n ): """ :type n: int :rtype: int """ dp = [ 0 ] * ( n + 1 ) dp [ 0 ] = dp [ 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 [ - 1 ] def numTrees ( self , n ): ans = 1 for i in range ( 1 , n + 1 ): ans = ans * ( n + i ) / i return ans / ( n + 1 )Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.