Given an integer n, return all the structurally unique BST's (binary search trees), which has exactly n nodes of unique values from 1 to n. Return the answer in any order.
Example 1:
Input: n = 3 Output: [[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3,2,null,1]]
Example 2:
Input: n = 1 Output: [[1]]
Constraints:
1 <= n <= 8Problem Overview: Given an integer n, generate every structurally unique Binary Search Tree that stores values from 1 to n. Each tree must follow BST ordering rules, and the result returns the root node of every valid tree configuration.
Approach 1: Recursive Tree Construction (Backtracking) (Time: O(Cn * n), Space: O(Cn * n))
This approach builds trees by choosing every number in the range [start, end] as the root. For a chosen root i, recursively generate all left subtrees from [start, i-1] and all right subtrees from [i+1, end]. Then combine every left subtree with every right subtree to form complete trees. The recursion explores all possible root choices, which naturally generates every valid structure. The total number of generated trees follows the Catalan sequence (Cn), which leads to exponential growth in the number of outputs.
This technique is essentially backtracking over root selections while constructing nodes that satisfy binary search tree ordering rules. It’s simple and mirrors the recursive definition of BSTs, making it the most common interview implementation.
Approach 2: Dynamic Programming with Memoization (Time: O(Cn * n), Space: O(Cn * n))
The recursive solution repeatedly recomputes subtrees for the same ranges. Memoization removes that duplication. Cache the result of generate(start, end) in a hash map or 2D table so the subtree list is built only once. When the recursion encounters the same range again, return the cached trees instead of rebuilding them.
This converts the brute recursive exploration into a classic dynamic programming problem over intervals. Each state represents all BSTs formed from a specific number range. Although the total number of produced trees is still Catalan-sized, memoization significantly reduces repeated recursion and improves practical performance.
Recommended for interviews: Start with the recursive tree construction because it clearly demonstrates understanding of BST structure and recursive decomposition. Then mention memoization as an optimization to eliminate repeated subtree generation. Interviewers typically expect the recursive formulation first, followed by the DP improvement.
This approach involves dividing the set of integers from 1 to n into left and right subtrees recursively for each possible root value. For each possible root node, the values less than the root form the left subtree and the values greater than the root form the right subtree. We repeat this process recursively to construct all unique BSTs by selecting each number in the range as the root.
This Python code defines a TreeNode class and a recursive function 'generate_trees' that builds all unique BSTs for integers between 'start' and 'end'. It selects each number as the root and recursively builds left and right subtrees.
Time Complexity: O(4^n / √n) where n is the number of nodes because it involves generating all unique trees which is a Catalan number problem.
Space Complexity: O(4^n / √n) for storing the results.
This approach involves leveraging dynamic programming to store results of previously evaluated subproblems to optimize the recursive solution. We maintain a memoization table to store precalculated trees for specific ranges, aiding efficient calculation by reducing the re-computation of the same subproblems.
This Python code employs memoization via the 'lru_cache' decorator to efficiently store and reuse the results of previously computed subproblems within the recursive 'generate_trees' function.
Time Complexity: O(4^n / √n) due to solving subproblems exactly once.
Space Complexity: O(4^n / √n) for storing the memoized results.
We design a function dfs(i, j) that returns all feasible binary search trees composed of [i, j], so the answer is dfs(1, n).
The execution steps of the function dfs(i, j) are as follows:
i > j, it means that there are no numbers to form a binary search tree at this time, so return a list consisting of a null node.i leq j, we enumerate the numbers v in [i, j] as the root node. The left subtree of the root node v is composed of [i, v - 1], and the right subtree is composed of [v + 1, j]. Finally, we take the Cartesian product of all combinations of the left and right subtrees, i.e., left times right, add the root node v, and get all binary search trees with v as the root node.The time complexity is O(n times G(n)), and the space complexity is O(n times G(n)). Where G(n) is the Catalan number.
| Approach | Complexity |
|---|---|
| Recursive Tree Construction | Time Complexity: O(4^n / √n) where n is the number of nodes because it involves generating all unique trees which is a Catalan number problem. |
| Dynamic Programming with Memoization | Time Complexity: O(4^n / √n) due to solving subproblems exactly once. |
| DFS (Depth-First Search) | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive Tree Construction (Backtracking) | O(Cn * n) | O(Cn * n) | Best for interviews and understanding BST structure. Straightforward recursion. |
| Dynamic Programming with Memoization | O(Cn * n) | O(Cn * n) | Use when avoiding repeated subtree computation. More efficient for larger n. |
Unique Binary Search Trees II - Leetcode 95 - Python • NeetCodeIO • 31,940 views views
Watch 9 more video solutions →Practice Unique Binary Search Trees II with our built-in code editor and test cases.
Practice on FleetCode