0980MediumDynamic ProgrammingBacktrackingTreeBinary Search TreeBinary Tree

Every Search Tree Over the First n Labels

Tracked in this browser only

Trains the technique from

LeetCode 95Unique Binary Search Trees II

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 search tree over the labels 1 through n holds each label once, and every label is larger than everything in its first slot's subtree and smaller than everything in its second slot's subtree.

Read a tree by visiting its top label, then everything in its first slot, then everything in its second slot, which gives one sequence of labels per tree and tells the trees apart.

Return the readings of all the distinct search trees over those labels, listed in increasing dictionary order.

Examples

Example 1

Input: n = 2
Output: [[1, 2], [2, 1]]

Either label may sit at the top. With the smaller on top the larger hangs in its second slot, and the other way round the smaller hangs in the first slot.

Example 2

Input: n = 4
Output: [[1, 2, 3, 4], [1, 2, 4, 3], [1, 3, 2, 4], [1, 4, 2, 3], [1, 4, 3, 2], [2, 1, 3, 4], [2, 1, 4, 3], [3, 1, 2, 4], [3, 2, 1, 4], [4, 1, 2, 3], [4, 1, 3, 2], [4, 2, 1, 3], [4, 3, 1, 2], [4, 3, 2, 1]]

Fourteen search trees hold four labels, and their top-first readings sorted give this list.

Example 3

Input: n = 5
Output: [[1, 2, 3, 4, 5], [1, 2, 3, 5, 4], [1, 2, 4, 3, 5], [1, 2, 5, 3, 4], [1, 2, 5, 4, 3], [1, 3, 2, 4, 5], [1, 3, 2, 5, 4], [1, 4, 2, 3, 5], [1, 4, 3, 2, 5], [1, 5, 2, 3, 4], [1, 5, 2, 4, 3], [1, 5, 3, 2, 4], [1, 5, 4, 2, 3], [1, 5, 4, 3, 2], [2, 1, 3, 4, 5], [2, 1, 3, 5, 4], [2, 1, 4, 3, 5], [2, 1, 5, 3, 4], [2, 1, 5, 4, 3], [3, 1, 2, 4, 5], [3, 1, 2, 5, 4], [3, 2, 1, 4, 5], [3, 2, 1, 5, 4], [4, 1, 2, 3, 5], [4, 1, 3, 2, 5], [4, 2, 1, 3, 5], [4, 3, 1, 2, 5], [4, 3, 2, 1, 5], [5, 1, 2, 3, 4], [5, 1, 2, 4, 3], [5, 1, 3, 2, 4], [5, 1, 4, 2, 3], [5, 1, 4, 3, 2], [5, 2, 1, 3, 4], [5, 2, 1, 4, 3], [5, 3, 1, 2, 4], [5, 3, 2, 1, 4], [5, 4, 1, 2, 3], [5, 4, 1, 3, 2], [5, 4, 2, 1, 3], [5, 4, 3, 1, 2], [5, 4, 3, 2, 1]]

Forty-two search trees hold five labels.

Constraints

1 <= n <= 8

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 generate_trees(n: int) -> list[list[int]]:

Java

public List<List<Integer>> generateTrees(int n)

The intended approach

Time O(C * n) for the C trees over n labels, C being the count of search trees.Space O(C * n) for the readings.

The label at the top splits the rest in two: everything below it goes into the first slot and everything above into the second, and neither side can borrow from the other. So the trees over a run of labels are built by choosing the top label, then pairing every tree over the labels below it with every tree over the labels above. Reading a tree top-first means the reading is the top label followed by the first slot's reading and then the second slot's, so the readings can be built the same way as the trees. Recursing over the runs of labels and joining the pieces gives every reading exactly once, and taking the tops in increasing order with the first slot's readings ordered too already produces them in dictionary order, though sorting at the end makes that certain.

Pythonentry point: generate_trees

def generate_trees(n):
    def build(lo, hi):
        if lo > hi:
            return [[]]
        out = []
        for top in range(lo, hi + 1):
            for left in build(lo, top - 1):
                for right in build(top + 1, hi):
                    out.append([top] + left + right)
        return out

    readings = build(1, n)
    readings.sort()
    return readings

The obvious version

Insert the labels into a search tree in every possible order, one order at a time, read each finished tree top-first, and keep the distinct readings sorted. Factorial in the label count and it builds the trees by insertion rather than by splitting the labels.

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_generate_trees(n):
    import itertools
    seen = set()
    for order in itertools.permutations(range(1, n + 1)):
        left = {}
        right = {}
        root = order[0]
        for label in order[1:]:
            at = root
            while True:
                if label < at:
                    if at in left:
                        at = left[at]
                    else:
                        left[at] = label
                        break
                else:
                    if at in right:
                        at = right[at]
                    else:
                        right[at] = label
                        break
        reading = []

        def walk(node):
            reading.append(node)
            if node in left:
                walk(left[node])
            if node in right:
                walk(right[node])

        walk(root)
        seen.add(tuple(reading))
    return [list(x) for x in sorted(seen)]

How this problem was checked

Reference solution executed against 8 test cases — 8 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