0547MediumMathDynamic ProgrammingTreeBinary Search TreeBinary Tree

Shapes of the Docket Registry

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def num_trees(n: int) -> int:

Java

public long numTrees(int n)

The intended approach

Time O(n^2): one inner sum of length size for each size up to n.Space O(n) for the table of counts.

The count depends only on how many dockets there are, never on which numbers they are, because the filing rule only cares about relative order. So fill a table of counts by registry size, starting with one way to build an empty registry. For a registry of size `size`, pick the docket that goes at the top: if `below` dockets are smaller than it then exactly those go into the lower branch and the remaining `size - 1 - below` go into the upper branch, and the two branches are chosen independently, so that top contributes the product of the two smaller table entries. Summing over every choice of top fills the entry for `size`.

Pythonentry point: num_trees

def num_trees(n):
    # O(n^2) time, O(n) space. Work upward by registry size. Once the docket at
    # the top of a registry of size k is chosen, the dockets numbered below it
    # must all sit in the lower branch and the ones above it in the upper
    # branch, and the two branches are filled independently, so the count for
    # size k is a sum of products of two smaller counts.
    dp = [0] * (n + 1)
    dp[0] = 1
    for size in range(1, n + 1):
        total = 0
        for below in range(size):
            total += dp[below] * dp[size - 1 - below]
        dp[size] = total
    return dp[n]

The obvious version

Count directly over docket number ranges: the number of registries holding the dockets from lo through hi is the sum, over each docket in that range taken as the top, of the count for the range below it times the count for the range above it. An empty range has one registry. Results per range are cached so each range is counted once.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_num_trees(n):
    memo = {}

    def count(lo, hi):
        if lo > hi:
            return 1
        key = (lo, hi)
        if key in memo:
            return memo[key]
        total = 0
        for top in range(lo, hi + 1):
            total += count(lo, top - 1) * count(top + 1, hi)
        memo[key] = total
        return total

    return count(1, n)

How this problem was checked

Reference solution executed against 10 test cases — 10 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in