Problem

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.

Examples

Example 1:

1
2

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:

1
2

Input: n = 1
Output: [[1]]

Solution

Method 1 - DFS

We can use DFS to do so:

  1. Base Case:
    • If n is zero, the result is an empty tree.
  2. Recursive Generation:
    • For each possible root value from 1 to n, recursively generate all possible left and right subtrees.
    • Combine each left and right subtree with the current root to form all possible unique BSTs.
  3. Combinations:
    • Each value i from 1 to n can be the root.
    • For each possible root, generate all combinations of left and right subtrees formed by the remaining values.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

class Solution {
    public List<TreeNode> generateTrees(int n) {
        if (n == 0) return new ArrayList<>();
        return generateTrees(1, n);
    }

    private List<TreeNode> generateTrees(int start, int end) {
        List<TreeNode> ans = new ArrayList<>();
        if (start > end) {
            ans.add(null);
            return ans;
        }
        for (int i = start; i <= end; i++) {
            List<TreeNode> leftSubtrees = generateTrees(start, i - 1);
            List<TreeNode> rightSubtrees = generateTrees(i + 1, end);
            for (TreeNode left : leftSubtrees) {
                for (TreeNode right : rightSubtrees) {
                    TreeNode root = new TreeNode(i);
                    root.left = left;
                    root.right = right;
                    ans.add(root);
                }
            }
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution:
    def generateTrees(self, n: int) -> List[Optional[TreeNode]]:
        if n == 0:
            return []
        return self.generate_trees(1, n)

    def generate_trees(self, start: int, end: int) -> List[Optional[TreeNode]]:
        if start > end:
            return [None]
        ans: List[Optional[TreeNode]] = []
        for i in range(start, end + 1):
            left_trees = self.generate_trees(start, i - 1)
            right_trees = self.generate_trees(i + 1, end)
            for left in left_trees:
                for right in right_trees:
                    root = TreeNode(i)
                    root.left = left
                    root.right = right
                    ans.append(root)
        return ans

Complexity

  • ⏰ Time complexity: O(2^n), due to the exponential number of possible BST structures.
  • 🧺 Space complexity: O(2^n) for storing all the unique trees.