# Unique Binary Search Trees
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/unique-binary-search-trees)
Canonical: https://scaleengineer.com/dsa/problems/unique-binary-search-trees
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** Tree, Binary Tree, Binary Search Tree
**Companies:** [Adobe](https://scaleengineer.com/companies/adobe), [Amazon](https://scaleengineer.com/companies/amazon), [Apple](https://scaleengineer.com/companies/apple), [Bloomberg](https://scaleengineer.com/companies/bloomberg), [Microsoft](https://scaleengineer.com/companies/microsoft), [Samsung](https://scaleengineer.com/companies/samsung), [TikTok](https://scaleengineer.com/companies/tiktok), [Yahoo](https://scaleengineer.com/companies/yahoo), [Zoho](https://scaleengineer.com/companies/zoho), [Snap](https://scaleengineer.com/companies/snap), [Clari](https://scaleengineer.com/companies/clari), [Tower Research Capital](https://scaleengineer.com/companies/tower-research-capital)
---
## 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:**

![](https://assets.glich.co/dsa/unique-binary-search-trees/image0.jpg) 

**Input:** n = 3
**Output:** 5

**Example 2:**

**Input:** n = 1
**Output:** 1

**Constraints:**

* `1 <= n <= 19`

# Approaches
## Brute Force Recursion
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.
**Time:** O(4^n / n^(3/2)) · **Space:** O(n)
**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 `n` greater than around 15.
### Explanation
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).

```java
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;
}
```
### Algorithm
- Define a function `numTrees(n)`.
- Handle the base cases: if `n` is 0 or 1, return 1.
- Initialize a variable `total` to 0.
- Iterate with a loop from `i = 1` to `n`. In each iteration, `i` represents the value of the root node.
- For each `i`, recursively call `numTrees(i - 1)` to get the count of unique left subtrees and `numTrees(n - i)` for the right subtrees.
- Multiply the results from the recursive calls and add the product to `total`.
- After the loop, return `total`.

## Dynamic Programming
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.
**Time:** O(n^2) · **Space:** O(n)
**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.
### Explanation
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]`.

```java
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];
}
```
### Algorithm
- Create an integer array `dp` of size `n + 1`.
- Initialize the base cases: `dp[0] = 1` and `dp[1] = 1`.
- Iterate with an outer loop from `i = 2` to `n`. This loop calculates the number of unique BSTs for `i` nodes.
- Inside the outer loop, use an inner loop from `j = 1` to `i`. This loop considers each `j` as the root of the BST with `i` nodes.
- In the inner loop, calculate the number of trees with `j` as the root: `dp[j-1] * dp[i-j]`. Add this to `dp[i]`.
- After the loops complete, `dp[n]` will hold the result for `n` nodes. Return `dp[n]`.

## Mathematical Formula (Catalan Numbers)
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.
**Time:** O(n) · **Space:** O(1)
**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 `long` is sufficient for the given constraints.
### Explanation
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.

```java
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));
}
```
### 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 a `long` variable `result` to 1.
- Loop from `i = 0` to `n-1`. In each step, update `result` by `result = result * (2n - i) / (i + 1)`. This computes `(2n choose n)`.
- After the loop, divide the `result` by `(n+1)` to get the n-th Catalan number.
- Cast the final `long` result to `int` and return.

# Solutions
### CSharp

```csharp
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];
    }
}
```

### Java

```java
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 ]; } }
```

### CPP

```cpp
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 ]; } };
```

### Python

```python
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 )
```