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 satisfy BST ordering and the result should return the root node of every valid structure.
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]. Combine each left subtree with each right subtree to form complete BSTs. The key insight is that BST structure depends entirely on which value is selected as the root and how the remaining values split into left and right ranges.
This technique naturally maps to backtracking over value ranges. The number of possible trees equals the Catalan number Cn, so the algorithm must construct roughly Cn trees, each taking up to O(n) work to link nodes.
Approach 2: Dynamic Programming with Memoization (Time: ~O(Cn * n), Space: ~O(Cn * n))
Recursive generation recomputes the same subtree ranges many times. Memoization avoids that by caching results for each interval (start, end). When the algorithm requests trees for the same range again, it returns the stored list instead of recomputing it.
This transforms the recursion into a classic dynamic programming problem over intervals. Each state represents all BSTs possible from a value range. By reusing computed subtrees, the algorithm significantly reduces repeated recursion while still enumerating all valid BST structures.
Recommended for interviews: Interviewers usually expect the recursive construction first because it clearly shows understanding of BST properties and recursive tree generation. Adding memoization demonstrates optimization skills and knowledge of interval-based dynamic programming. Both approaches share the same theoretical complexity because the algorithm must output every valid BST.
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.
C
C++
Java
C#
JavaScript
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.
C++
Java
Time Complexity: O(4^n / √n) due to solving subproblems exactly once.
Space Complexity: O(4^n / √n) for storing the memoized results.
| 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. |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive Tree Construction | ~O(Cn * n) | ~O(Cn * n) | Best for understanding BST structure generation and interview explanations |
| Dynamic Programming with Memoization | ~O(Cn * n) | ~O(Cn * n) | Use when avoiding repeated recursion over the same value ranges |
Unique Binary Search Trees - Leetcode 96 - Python Dynamic Programming • NeetCode • 77,933 views views
Watch 9 more video solutions →Practice Unique Binary Search Trees II with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor