Last updated on March 7th, 2025 at 07:20 pm

Here, we see a Unique Binary Search Trees LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.

List of all LeetCode Solution

Topics

Dynamic Programming, Tree

Companies

Snapchat

Level of Question

Medium

Unique Binary Search Trees LeetCode Solution

1. Problem Statement

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

2. Coding Pattern Used in Solution

The coding pattern used in this code is Dynamic Programming. Specifically, it is solving the Catalan Number Problem using a bottom-up dynamic programming approach. The problem involves calculating the number of unique Binary Search Trees (BSTs) that can be formed with n nodes, which is a classic application of the Catalan number formula.

3. Code Implementation in Different Languages

3.1 Unique Binary Search Trees C++

class Solution {
public:
    int numTrees(int n) {
        vector<int>result(n+1,0); //Initializing vector with 0
        result[1]=result[0]=1;
        for(int i=2;i<=n;i++)
        {
            for(int j=0;j<i;j++)
            {
                result[i]+=result[j]*result[i-j-1]; //Calculating C(i) to use for C(i+1) and storing it in result
            }
        }
        return result[n]; //return answer        
    }
};

3.2 Unique Binary Search Trees Java

class Solution {
    public int numTrees(int n) {
    int [] G = new int[n+1];
    G[0] = G[1] = 1;
    
   for(int i=2; i<=n; ++i) {
     for(int j=1; j<=i; ++j) {
       G[i] += G[j-1] * G[i-j];
     }
   }
   return G[n];    
     }
 }

3.3 Unique Binary Search Trees JavaScript

var numTrees = function(n) {
    let G = new Array(n+1).fill(0);
    G[0] = 1;
    G[1] = 1;
    for (let i=2;i<=n;i++) {
        for (let j=1;j<=i;j++) {
            G[i]+=G[j-1] * G[i - j];
        }
    }
    return G[n];    
};

3.4 Unique Binary Search Trees Python

class Solution(object):
    def numTrees(self, n):
        dp = [0 for i in range(n+1)]
        dp[0] = dp[1] = 1
    
        for i in range(2, n+1) :
            for j in range(i) :
                dp[i] += dp[j] * dp[(i-1)-j]
    
        return dp[-1]

4. Time and Space Complexity

	Time Complexity	Space Complexity
C++	O(n2)	O(n)
Java	O(n2)	O(n)
JavaScript	O(n2)	O(n)
Python	O(n2)	O(n)

• The code is solving the Catalan Number Problem using Dynamic Programming.
• The time complexity is quadratic because of the nested loops, and the space complexity is linear due to the use of the DP array.
• The approach is efficient for moderate values of n but may become computationally expensive for very large n due to the O(n²) time complexity.