Unique Binary Search Trees

Medium
577.

Unique Binary Search Trees

Unique Binary Search Trees is a medium coding problem on dynamic programming and math, asked in Amazon, Google and Adobe interviews.

Given an integer n, return the number of structurally distinct binary search trees that hold exactly the values 1 through n.

Example 1

Input
n = 3
Output
5

Example 2

Input
n = 1
Output
1

Example 3

Input
n = 5
Output
42

Constraints

  • 1 <= n <= 19
  • The answer fits in a 32-bit integer.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} n
 * @return {number}
 */
var numTrees = function(n) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Unique Binary Search Trees — Solution in Python, Java & C++

Unique Binary Search Trees solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Unique Binary Search Trees is a medium coding problem on dynamic programming and math, asked in Amazon, Google and Adobe interviews.

  • Difficulty: Medium
  • Topics: Dynamic Programming, Math
  • Asked at: Amazon, Google, Adobe
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Given an integer n, return the number of structurally distinct binary search trees that hold exactly the values 1 through n.

Example 1

Input: n = 3
Output: 5

Example 2

Input: n = 1
Output: 1

Example 3

Input: n = 5
Output: 42

Constraints

  • 1 <= n <= 19
  • The answer fits in a 32-bit integer.

Hints for Unique Binary Search Trees

  1. Hint 1

    Fix which value sits at the root — say k.

  2. Hint 2

    Everything below k forms the left subtree and everything above forms the right, independently.

  3. Hint 3

    So G(n) = Σ G(k-1) · G(n-k) for k from 1 to n, with G(0) = 1.

How to solve Unique Binary Search Trees

Choosing the root splits the value range into two independent sub-ranges. The count depends only on the sizes of those ranges, not on the actual values — which gives the Catalan recurrence.

Approach

  1. Set G[0] = 1 (the empty tree counts as one shape).
  2. For each i from 1 to n, sum G[root-1] * G[i-root] over every possible root position.
  3. Return G[n].

Why it works

A BST on {1..n} with root k has a left subtree over {1..k-1} and a right subtree over {k+1..n}. The shapes available depend only on how many values each side holds, so the counts multiply and the roots partition the possibilities.

Complexity

  • Time — O(n²)
  • Space — O(n)

Pitfalls

  • G[0] = 0 collapses everything to zero — an empty subtree is one valid shape.
  • At n = 19 the answer is 1,767,263,190, just inside a signed 32-bit integer; larger n would overflow.
  • The direct Catalan formula works too but needs care with integer division.

Reference solution

Python

def numTrees(n: int) -> int:
    g = [0] * (n + 1)
    g[0] = 1
    for i in range(1, n + 1):
        for root in range(1, i + 1):
            g[i] += g[root - 1] * g[i - root]
    return g[n]

Java

public static int numTrees(int n) {
    long[] g = new long[n + 1];
    g[0] = 1;
    for (int i = 1; i <= n; i++) {
        for (int root = 1; root <= i; root++) {
            g[i] += g[root - 1] * g[i - root];
        }
    }
    return (int) g[n];
}

C++

int numTrees(int n) {
    vector<long long> g(n + 1, 0);
    g[0] = 1;
    for (int i = 1; i <= n; i++) {
        for (int root = 1; root <= i; root++) {
            g[i] += g[root - 1] * g[i - root];
        }
    }
    return (int) g[n];
}

JavaScript

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

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 402 dynamic programming problems · the whole catalogue

Learn the technique: Dynamic Programming