Skip to main content
Talentd

Unique Binary Search Trees - Solution & Explanation

MediumMathDynamic ProgrammingTreeBinary Search Tree15 min readAsked at: Amazon, Microsoft, Meta +7
Practice this problem

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

 

Constraints:

  • 1 <= n <= 19

Approach Overview

Problem Overview: Given an integer n, count how many structurally unique binary search trees can be built using values from 1 to n. Each number must appear exactly once. Different tree shapes count as different BSTs even if they contain the same values.

Approach 1: Dynamic Programming (Time: O(n2), Space: O(n))

The key observation comes from the BST property: when you pick a value i as the root, all numbers 1..i-1 must form the left subtree and i+1..n must form the right subtree. The number of unique BSTs with i as root equals the number of possible left subtrees multiplied by the number of right subtrees. Define dp[k] as the number of BSTs that can be formed using k nodes. For each total node count k, iterate every node as root and accumulate dp[left] * dp[right]. This bottom-up dynamic programming approach builds answers from smaller subtree sizes.

Initialize dp[0] = 1 and dp[1] = 1 because an empty tree and a single-node tree both have exactly one valid structure. For each nodes from 2 to n, iterate possible roots and compute subtree combinations. The nested iteration leads to O(n2) time complexity. Space stays O(n) for the DP array.

Approach 2: Catalan Number Formula (Time: O(n), Space: O(1))

This problem is a direct application of the Catalan sequence, a classic result from math and combinatorics. The number of unique BSTs with n nodes equals the nth Catalan number. The closed-form formula is C(n) = (1 / (n + 1)) * binomial(2n, n). Instead of computing large factorials, you can iteratively calculate the binomial coefficient using multiplication and division to avoid overflow.

The Catalan interpretation works because every BST can be uniquely defined by choosing a root and recursively combining valid left and right subtree counts. This is exactly the recurrence used in the DP solution, but the mathematical formula collapses the recurrence into a direct computation. The iterative Catalan computation runs in O(n) time with constant extra space.

Recommended for interviews: Start with the Dynamic Programming approach. It demonstrates understanding of the BST root-partition idea and shows you can translate a recursive counting problem into a DP recurrence. Interviewers usually expect dp[n] = sum(dp[left] * dp[right]). Mentioning the Catalan number formula afterward signals deeper algorithm knowledge and familiarity with common combinatorial patterns.

Approach 1: Dynamic Programming

The problem can be efficiently solved using Dynamic Programming. We notice that the number of unique BSTs can be determined as follows: for each node i from 1 to n, calculate the number of left and right subtrees which can form by considering i as the root. We can store these results in a table to avoid redundant work. The relationship can be expressed as:

G(n) = \sum_{i=1}^{n} (G(i-1) * G(n-i))

where G(0) = 1 and G(1) = 1 are base cases.

This C solution uses a dynamic programming array dp to store the number of unique BSTs for each number of nodes up to n. We initialize dp[0] and dp[1] to 1 as base cases. Then, for each number i, the number of unique BSTs can be calculated using previous results.

Code

CC++JavaPythonC#JavaScriptGoTypeScriptRust

C

C++

Java

Python

C#

JavaScript

Go

TypeScript

Rust

Complexity

Time Complexity: O(n^2)
Space Complexity: O(n)

Try this approach in the editor →

Approach 2: Catalan Number Formula

Using the Catalan number formula provides a mathematical way to solve the problem directly without iteration for up to moderate n. The nth catalan number C(n) is given by:

C(n) = \frac{1}{n+1}\binom{2n}{n}

The C(n) represents the number of unique BSTs for n nodes. This can be computed efficiently using mathematical operations.

This C solution uses the Catalan number formula leveraging combination calculations. The function binomialCoeff computes C(2n, n) before dividing by n+1 to get the nth Catalan number.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Dynamic Programming

Time Complexity: O(n^2)
Space Complexity: O(n)

Catalan Number Formula

Time Complexity: O(n)
Space Complexity: O(1)

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Dynamic ProgrammingO(n^2)O(n)Best interview explanation; shows BST root partition and DP recurrence clearly
Catalan Number FormulaO(n)O(1)When you recognize the Catalan pattern and want a mathematically optimized solution

Video Solution

Unique Binary Search Trees - Leetcode 96 - Python Dynamic Programming • NeetCode • 94,107 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Unique Binary Search Trees easy or hard?
Unique Binary Search Trees is rated Medium difficulty on LeetCode with an acceptance rate around 63%. The challenge is recognizing the recursive subtree counting pattern and converting it into a dynamic programming recurrence.
Unique Binary Search Trees Python/Java solution
In Python or Java, the typical solution builds a DP array where dp[i] stores the number of BSTs using i nodes. For each i from 2 to n, iterate root from 1..i and accumulate dp[root-1] * dp[i-root]. Both languages implement this in O(n^2) time and O(n) space.
How to solve Unique Binary Search Trees in O(n)?
Use the Catalan number formula C(n) = (1 / (n + 1)) * binomial(2n, n). Instead of computing factorials, iteratively calculate the binomial coefficient to avoid overflow. This computes the result in O(n) time and constant space.
What is the best approach for Unique Binary Search Trees?
Dynamic Programming is the most commonly used approach in interviews. Define dp[n] as the number of unique BSTs that can be formed with n nodes and compute dp[n] = sum(dp[left] * dp[right]) for all possible roots. This runs in O(n^2) time and O(n) space and clearly demonstrates the BST root partition idea.
Is Unique Binary Search Trees asked at Google/Amazon/Meta?
Unique Binary Search Trees is a classic dynamic programming and combinatorics problem frequently asked in interviews at companies like Amazon, Google, and Meta. It tests understanding of BST properties, recursion-to-DP transitions, and recognition of Catalan number patterns.
What data structure is used in Unique Binary Search Trees?
The problem revolves around Binary Search Trees conceptually, but the implementation mainly uses a dynamic programming array to store counts of subtree combinations. The DP table captures how many BST structures can be formed for each subtree size.
What is the time complexity of Unique Binary Search Trees?
The standard dynamic programming solution runs in O(n^2) time because for each node count you iterate over all possible roots. Space complexity is O(n) for the DP array. Using the Catalan number formula reduces the computation to O(n) time with O(1) extra space.

Ready to solve this problem?

Practice Unique Binary Search Trees with our built-in code editor and test cases.

Practice on FleetCode
Previous

Unique Binary Search Trees II