DSA problem
Unique Binary Search Trees II
Given an integer n, return all the structurally unique BSTs (binary search trees) that store exactly n nodes of unique values from 1 to n. The answer may be returned in any order. Two BSTs are considered the same only if their structure and node values match at every position.
The counting version of this problem (Unique Binary Search Trees I) asks merely how many such trees exist — the Catalan number C_n. Here we must materialize every one of them. The key structural observation is that a BST on {lo, lo+1, ..., hi} is uniquely determined by three pieces: a chosen root i in [lo..hi], a left BST built from {lo..i-1}, and a right BST built from {i+1..hi}.
That observation gives a clean recursive construction. For each candidate root i we recursively generate every valid left subtree and every valid right subtree, then form the Cartesian product: for every L in the left list and every R in the right list, create a new root node with value i, left child L, and right child R. The base case is an empty range, which returns the single-element list [null] so the product still happens once and yields a valid subtree.
The work is bounded by the number of trees we have to emit: there are C_n distinct BSTs and each contains n nodes. With memoization on the range bounds you can avoid rebuilding subtrees with the same shape repeatedly. Total time is O(n * C_n) and total space is the size of the output plus the recursion stack of depth n.
Examples
n = 3[[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3,2,null,1]]n = 1[[1]]n = 2[[1,null,2],[2,1]]Constraints
- 1 <= n <= 8
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.