Show problems as
Classic problem #95MediumDynamic ProgrammingBacktrackingTreeBinary Search TreeBinary Tree

Unique Binary Search Trees II

Real-world version: Every Search Tree Over the First n Labels
Tracked in this browser only
Read Unique Binary Search Trees II on LeetCode(opens in a new tab)

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

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

Python
def generate_trees(n: int) -> list[list[int]]:
Java
public List<List<Integer>> generateTrees(int n)

More on the same topics