96. Unique Binary Search Trees

Medium

Problem Description

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.

Examples

Example 1:
Input: n = 3
Output: 5
Explanation: The 5 unique BSTs are:
   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

Example 2:
Input: n = 1
Output: 1
Jump to Solution: Python Java C++ JavaScript C#

Python Solution


def numTrees(n: int) -> int:
    # dp[i] represents the number of unique BSTs with i nodes
    dp = [0] * (n + 1)
    dp[0] = 1  # Empty tree is also a valid BST
    
    # For each number of nodes
    for i in range(1, n + 1):
        # For each root value
        for j in range(1, i + 1):
            # Number of unique BSTs = left subtree possibilities * right subtree possibilities
            dp[i] += dp[j - 1] * dp[i - j]
    
    return dp[n]

Java Solution


class Solution {
    public int numTrees(int n) {
        // dp[i] represents the number of unique BSTs with i nodes
        int[] dp = new int[n + 1];
        dp[0] = 1;  // Empty tree is also a valid BST
        
        // For each number of nodes
        for (int i = 1; i <= n; i++) {
            // For each root value
            for (int j = 1; j <= i; j++) {
                // Number of unique BSTs = left subtree possibilities * right subtree possibilities
                dp[i] += dp[j - 1] * dp[i - j];
            }
        }
        
        return dp[n];
    }
}

C++ Solution


class Solution {
public:
    int numTrees(int n) {
        // dp[i] represents the number of unique BSTs with i nodes
        vector dp(n + 1, 0);
        dp[0] = 1;  // Empty tree is also a valid BST
        
        // For each number of nodes
        for (int i = 1; i <= n; i++) {
            // For each root value
            for (int j = 1; j <= i; j++) {
                // Number of unique BSTs = left subtree possibilities * right subtree possibilities
                dp[i] += dp[j - 1] * dp[i - j];
            }
        }
        
        return dp[n];
    }
};

JavaScript Solution


/**
 * @param {number} n
 * @return {number}
 */
var numTrees = function(n) {
    // dp[i] represents the number of unique BSTs with i nodes
    const dp = new Array(n + 1).fill(0);
    dp[0] = 1;  // Empty tree is also a valid BST
    
    // For each number of nodes
    for (let i = 1; i <= n; i++) {
        // For each root value
        for (let j = 1; j <= i; j++) {
            // Number of unique BSTs = left subtree possibilities * right subtree possibilities
            dp[i] += dp[j - 1] * dp[i - j];
        }
    }
    
    return dp[n];
};

C# Solution


public class Solution {
    public int NumTrees(int n) {
        // dp[i] represents the number of unique BSTs with i nodes
        int[] dp = new int[n + 1];
        dp[0] = 1;  // Empty tree is also a valid BST
        
        // For each number of nodes
        for (int i = 1; i <= n; i++) {
            // For each root value
            for (int j = 1; j <= i; j++) {
                // Number of unique BSTs = left subtree possibilities * right subtree possibilities
                dp[i] += dp[j - 1] * dp[i - j];
            }
        }
        
        return dp[n];
    }
}

Complexity Analysis

Solution Explanation

This solution uses dynamic programming to calculate Catalan numbers:

Key points: