Abstract / Summary

Generate all possible binary search trees for a given number of nodes without duplicates

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 63% (900k+ submissions).

Typical patterns to solve this problem:

• Backtracking
• Binary Search Tree
• Binary Tree
• Dynamic Programming
• Tree

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation generates all structurally unique binary search trees (BSTs) that can be built from the integers 1 through n. It does so by enumerating every permutation of the input numbers, inserting the values into a BST in the order dictated by the permutation, and then using a string representation of each tree to eliminate duplicates. The final collection of distinct tree roots is returned as a vector.

Key Steps

Preparing the integer sequence

The algorithm starts by constructing a vector that holds the numbers from 1 to n. This vector serves as the source for permutation generation.

vector<int> nums;
for (int i = 1; i <= n; i++)
    nums.push_back(i);

Inserting a value into a BST

A helper function add receives a subtree root and a value to insert. If the current root is null, a new node is allocated. Otherwise the function recurses left when the value is smaller than the node’s key, or right when it is greater or equal. The function returns the (possibly new) root of the subtree.

TreeNode* add(TreeNode* root, int value)
{
    if (!root)
        return new TreeNode(value);

    if (value < root->val)
        root->left = add(root->left, value);
    else
        root->right = add(root->right, value);
    return root;
}

Serializing a BST to a canonical string

To compare trees for structural equality, the flatten routine produces a preorder-style string that records the presence of left and right children with the markers L and R, and inserts the node’s value between them. An empty subtree yields an empty string, ensuring that different shapes generate distinct serializations.

string flatten(TreeNode* root)
{
    if (!root)
        return "";

    return "L" + flatten(root->left) + "V" + to_string(root->val) + "R" + flatten(root->right);
}

Enumerating permutations and building trees

The core loop uses next_permutation to walk through every ordering of the numbers. For each permutation, a fresh BST is built by repeatedly calling add. The resulting tree is then serialized, and the pair (serialization, root) is stored in a map. Because map keys are unique, any duplicate tree structures produced by different permutations automatically collapse to a single entry.

do
{
    TreeNode* root = nullptr;
    for (auto n : nums)
        root = add(root, n);

    trees[flatten(root)] = root;
} while (next_permutation(nums.begin(), nums.end()));

Extracting the distinct trees

After all permutations have been processed, the values of the map (the unique tree roots) are collected into a vector that forms the function’s return value.

vector<TreeNode*> result;
for (auto t : trees)
    result.push_back(t.second);
return result;

Edge Cases Handled

When n equals 0, the initial loop that fills nums does not execute, leaving the vector empty. The subsequent do-while loop still runs once because do executes before the permutation check. Inside that iteration, the inner for loop over nums performs no insertions, leaving root as nullptr. The flatten call on a null pointer returns an empty string, which becomes the sole key in the map. Consequently, the function returns a vector containing a single nullptr, representing the empty tree case.

The add function gracefully handles insertion into an empty subtree by allocating a new node when the supplied root pointer is null. This ensures that the first element of any permutation always becomes the tree’s root without special-case code.

The serialization routine treats missing children uniformly: both left and right null pointers contribute nothing to the string, but the surrounding L and R markers remain, preserving the positional information of existing subtrees. This design prevents two different shapes from collapsing to the same string.

Performance Optimizations Observed

The algorithm leverages the standard library’s next_permutation, which generates permutations in lexicographic order using an in-place rearrangement of the nums vector. This avoids the overhead of constructing new containers for each ordering.

Insertion into the BST is performed recursively, reusing the same node objects for the duration of a single permutation’s construction. No intermediate containers are created to hold partial trees, reducing allocation churn.

Deduplication relies on a map keyed by the serialized representation. Because the map maintains sorted order, look-ups and insertions are logarithmic in the number of distinct trees encountered so far, providing a balanced trade-off between speed and memory usage compared with a naïve linear search.

The serialization function builds the string using concatenation of small literals and the result of recursive calls. Since each node contributes a fixed set of characters, the total work per tree scales linearly with the number of nodes, and the generated strings serve as compact identifiers for structural comparison.

Overall, the code combines standard library utilities with concise recursive helpers to achieve its goal without extraneous data structures or repeated traversals.

Imagine you have a big box of numbered blocks. This computer code acts like a very organized builder who wants to see how many different ways those blocks can be stacked into a tree shape.

First, the builder takes all the numbers from one up to the number that you picked. The builder puts them in a line, almost like waiting in a row for a turn to play. Then, the builder picks up the first number and uses it to start a tree. Each friend after that looks at the tree and decides if they belong on the left side or the right side by checking if their number is smaller or bigger than the ones already there.

After the tree is finished, the builder takes a special picture of it by walking through it and writing down a secret code. This code shows exactly where every number is sitting. The builder does this over and over again, changing the order of the numbers in line every single time.

If the builder ever makes a tree that looks exactly like one already created, it just keeps the old one and moves on. Once all the different ways to line up the blocks have been tried, the finished collection of unique trees is gathered together into one big pile.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: factorial
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Python	Java								TS
	WalkCCC	C++	Python	Java
	leetcode.ca	C++	Python	Java	Rust					Go		TS
	LeetcodeHelp	C++	Python	Java
	MemoryLimitExceeded	C++	Python
	Progiez	C++	Python	Java
github	aylei				Rust
	begeekmyfriend										C
	BigEggStudy						C#
	black-shadows	C++
	charles-wangkai			Java
	chenyanzhe	C++
	everthis					JS
	fartem								Ruby
	fengvyi	C++
	fpdjsns	C++
	gaosq0604		Python
	Garvit244		Python
	gouthampradhan			Java
	halfrost									Go
	haoel		Python
	JoshCrozier					JS
	keineahnung2345	C++
	lennylxx	C++
	linouk23	C++
	lkwq007		Python
	luangong	C++
	MacJim	C++
	martianoff							Scala
	qiyuangong		Python
	ruoru				Rust
	suxrobGM						C#
	vthwang			Java
	wisdompeak	C++
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, Rust, TypeScript
LeetcodeHelp	C++, Java, Python
MemoryLimitExceeded	Python, C++
Progiez	C++, Java, Python
aylei	Rust
begeekmyfriend	C
BigEggStudy	C#
black-shadows	C++, C++
charles-wangkai	Java
chenyanzhe	C++
everthis	JavaScript
fartem	Ruby
fengvyi	C++
fpdjsns	C++
gaosq0604	Python
Garvit244	Python
gouthampradhan	Java
halfrost	Go
haoel	Python
JoshCrozier	JavaScript
keineahnung2345	C++
lennylxx	C++
linouk23	C++
lkwq007	Python
luangong	C++
MacJim	C++
martianoff	Scala
qiyuangong	Python
ruoru	Rust
suxrobGM	C#
vthwang	Java
wisdompeak	C++
zfang399	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality