Show problems as
Classic problem #96MediumMathDynamic ProgrammingTreeBinary Search TreeBinary Tree

Unique Binary Search Trees

Real-world version: Shapes of the Docket Registry
Tracked in this browser only
Read Unique Binary Search Trees on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A claims office files dockets numbered 1 through n into a search tree. Each docket occupies exactly one node, and each node has at most two nodes hanging off it, one called its lower child and one called its upper child.

The filing rule is that for every node, every docket sitting anywhere beneath its lower child carries a smaller number, and every docket sitting anywhere beneath its upper child carries a larger number.

Two registries are considered different when some docket has a different lower child or a different upper child in one than in the other. Return how many different registries can be built from dockets 1 through n.

Examples

Example 1

Input
n = 6
Output
132

Six dockets can be filed in 132 different registries.

Example 2

Input
n = 9
Output
4862

Nine dockets can be filed in 4862 different registries.

Example 3

Input
n = 4
Output
14

With four dockets there are 14 registries. Putting docket 2 at the top, for instance, forces docket 1 into its lower branch and leaves dockets 3 and 4 for the upper branch, which they can fill in two ways.

Constraints

  • 1 <= n <= 25
  • The largest allowed n gives an answer of 4861946401452, so every answer stays below 5 * 10^12.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def num_trees(n: int) -> int:
Java
public long numTrees(int n)

More on the same topics