Problem Description

Given an integer n, you need to generate all structurally unique Binary Search Trees (BSTs) that can be constructed using exactly n nodes, where each node has a unique value from 1 to n.

A Binary Search Tree follows the property where:

• The left subtree of a node contains only nodes with values less than the node's value
• The right subtree of a node contains only nodes with values greater than the node's value
• Both left and right subtrees must also be binary search trees

The task is to return all possible unique BST structures. The trees should be returned as a list of root nodes, and the answer can be in any order.

For example, if n = 3, you would use values 1, 2, 3 to construct all possible BSTs. Different arrangements of these values as nodes will create different tree structures. Some possible structures include:

• Tree with 1 as root, 2 in the right subtree, and 3 as the right child of 2
• Tree with 2 as root, 1 as left child, and 3 as right child
• Tree with 3 as root, 2 in the left subtree, and 1 as the left child of 2

The solution uses a recursive approach where for each possible root value v in range [i, j], it generates all possible left subtrees using values [i, v-1] and all possible right subtrees using values [v+1, j]. Then it combines each left subtree with each right subtree to create all possible BSTs with v as the root.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• No: While BSTs are tree structures, this problem is not about traversing or analyzing an existing graph. Instead, we need to generate all possible tree structures.

Need to solve for kth smallest/largest?

• No: The problem asks for all possible BST structures, not finding a specific kth element.

Involves Linked Lists?

• No: The problem involves binary trees, not linked lists.

Does the problem have small constraints?

• Yes: The problem typically has small constraints since generating all unique BSTs grows exponentially. For practical purposes, n is usually small (often ≤ 8 or similar) because the number of unique BSTs is the Catalan number C(n), which grows very quickly.

Brute force / Backtracking?

• Yes: We need to explore all possible combinations of BST structures. For each possible root value, we recursively generate all possible left and right subtrees, then combine them. This is a classic backtracking pattern where we:
  1. Choose a root value
  2. Recursively generate all left subtrees
  3. Recursively generate all right subtrees
  4. Combine each left-right pair with the chosen root

Conclusion: The flowchart correctly identifies that this problem requires a Backtracking approach. The recursive nature of generating all possible BST structures by trying each value as a root and combining all possible subtree configurations is a textbook example of backtracking.

Intuition

When we need to generate all possible BSTs with values from 1 to n, the key insight is that any number can be the root. If we choose value v as the root, then all values less than v must go in the left subtree, and all values greater than v must go in the right subtree - this is the fundamental BST property.

Let's think about this with a small example. If n = 3, we have values [1, 2, 3]. If we pick 2 as the root:

• The left subtree can only contain 1
• The right subtree can only contain 3

But what if we pick 1 as the root? Then all values [2, 3] must go to the right subtree, and we need to figure out all possible ways to arrange them as a BST.

This naturally leads to a recursive pattern: to generate all BSTs for range [i, j], we:

1. Try each value v in [i, j] as the root
2. Generate all possible left subtrees using values [i, v-1]
3. Generate all possible right subtrees using values [v+1, j]
4. Combine each left subtree with each right subtree

The beauty of this approach is that each subproblem (generating trees for a smaller range) has the same structure as the original problem. When we reach a range where i > j, it means we have no values to create a tree, so we return [None] to represent an empty subtree.

The combination step is crucial - if we have 2 possible left subtrees and 3 possible right subtrees for a given root, we create 2 × 3 = 6 different trees with that root. This Cartesian product ensures we generate all unique combinations.

This recursive decomposition with the backtracking pattern allows us to systematically explore all possibilities without missing any valid BST structure.

Learn more about Tree, Binary Search Tree, Dynamic Programming, Backtracking and Binary Tree patterns.

Solution Approach

The solution implements a recursive depth-first search (DFS) function that generates all possible BSTs for a given range of values.

Core Function Design:

We define a helper function dfs(i, j) that returns a list of all possible BST root nodes that can be formed using values from i to j inclusive. The main function simply calls dfs(1, n) to generate all BSTs using values from 1 to n.

Base Case:

When i > j, it means we have an empty range with no values to form a tree. In this case, we return [None] - a list containing a single None value. This is important because it represents an empty subtree, which is necessary when a node has no left or right child.

Recursive Case:

For a valid range [i, j], we iterate through each possible root value v from i to j:

1. Generate Left Subtrees: Call dfs(i, v-1) to get all possible BSTs that can be formed using values less than v. These will become the left subtrees.

2. Generate Right Subtrees: Call dfs(v+1, j) to get all possible BSTs that can be formed using values greater than v. These will become the right subtrees.

3. Combine Subtrees: For each combination of left and right subtrees, create a new tree node with value v as the root. This is done using nested loops:

   for l in left:
       for r in right:
           ans.append(TreeNode(v, l, r))

Why This Works:

The algorithm leverages the BST property that all values in the left subtree must be less than the root, and all values in the right subtree must be greater than the root. By recursively solving smaller subproblems and combining their results, we ensure that:

• Every possible value gets a chance to be the root
• For each root choice, we explore all valid left and right subtree combinations
• The Cartesian product of left and right subtrees ensures we don't miss any unique structure

Time Complexity Analysis:

The number of unique BSTs with n nodes is the n-th Catalan number, which is approximately 4^n / (n^(3/2)). Since we generate all these trees and each tree has n nodes, the time complexity is O(4^n / sqrt(n)).

Space Complexity:

The space complexity is dominated by the output, which stores all the generated trees. This is also O(4^n / sqrt(n)) multiplied by n for the nodes in each tree.

Example Walkthrough

Let's walk through generating all BSTs for n = 3 using values [1, 2, 3].

Initial Call: dfs(1, 3) - generate all BSTs using values from 1 to 3.

We'll try each value as the root:

Case 1: Root = 1

• Left subtrees: dfs(1, 0) → returns [None] (empty range)

• Right subtrees: dfs(2, 3) → need to generate BSTs with values [2, 3]

  For dfs(2, 3):

  • When root = 2: left=dfs(2,1)=[None], right=dfs(3,3)=[TreeNode(3)] → Creates tree: 2 (left=None, right=3)
  • When root = 3: left=dfs(2,2)=[TreeNode(2)], right=dfs(4,3)=[None] → Creates tree: 3 (left=2, right=None)

  So dfs(2, 3) returns two trees: [2→3, 3←2]

• Combining for root=1: Each None left × each right tree

  • Result: Two trees with root 1:

        1           1
         \           \
          2           3
           \         /
            3       2

Case 2: Root = 2

• Left subtrees: dfs(1, 1) → returns [TreeNode(1)]
• Right subtrees: dfs(3, 3) → returns [TreeNode(3)]
• Combining: 1 left × 1 right = 1 tree
  • Result: One tree with root 2:

        2
       / \
      1   3

Case 3: Root = 3

• Left subtrees: dfs(1, 2) → need to generate BSTs with values [1, 2]

  For dfs(1, 2):

  • When root = 1: left=[None], right=[TreeNode(2)] → Creates tree: 1→2
  • When root = 2: left=[TreeNode(1)], right=[None] → Creates tree: 2←1

  So dfs(1, 2) returns two trees: [1→2, 2←1]

• Right subtrees: dfs(4, 3) → returns [None] (empty range)

• Combining for root=3: Each left tree × each None right

  • Result: Two trees with root 3:

        3           3
       /           /
      1           2
       \         /
        2       1

Final Result: Combining all cases, we get 5 unique BSTs total:

    1        1        2        3       3
     \        \      / \      /       /
      2        3    1   3    1       2
       \      /              \      /
        3    2                2    1

The recursive approach ensures we systematically explore every valid combination by:

1. Trying each value as a potential root
2. Recursively generating all valid left and right subtrees
3. Combining them using the Cartesian product to create all possible trees

Solution Implementation

Time and Space Complexity

The time complexity is O(n × G(n)), where G(n) is the nth Catalan number.

The recursive function dfs(i, j) generates all structurally unique BSTs with values from i to j. For each value v in the range [i, j], it serves as the root, and we recursively generate all possible left subtrees (values from i to v-1) and right subtrees (values from v+1 to j). The total number of unique BSTs with n nodes is the nth Catalan number G(n) = C(2n, n) / (n+1), which grows as O(4^n / n^(3/2)).

For each of the G(n) trees generated, we need to construct the tree by iterating through all possible root values (n choices) and combining left and right subtrees. The time to construct each tree involves creating nodes and linking them, which takes O(n) time per tree. Therefore, the total time complexity is O(n × G(n)).

The space complexity is O(n × G(n)).

The space is dominated by the storage of all generated trees. Since we generate G(n) unique BSTs and each tree contains exactly n nodes, the total space required to store all trees is O(n × G(n)). Additionally, the recursion stack depth is at most O(n) (when generating a skewed tree), but this is negligible compared to the space needed to store all the trees.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Base Case Handling

A frequent mistake is returning an empty list [] instead of [None] when start > end. This seems logical since there are no nodes to create, but it causes the algorithm to fail.

Why this is wrong:

# INCORRECT
if start > end:
    return []  # This breaks the algorithm!

When generating combinations of left and right subtrees, if either returns an empty list, the nested loops won't execute at all:

for left_subtree in []:  # This loop never executes
    for right_subtree in right_subtrees:
        # This code is never reached

This means nodes with only one child wouldn't be generated properly. For example, a node with value 1 should have no left child (None) and potentially a right subtree.

Correct approach:

# CORRECT
if start > end:
    return [None]  # Represents an empty subtree

2. Creating Shared Node References

Another critical mistake is trying to reuse the same node object in multiple trees, which creates shared references and invalid tree structures.

Problematic approach:

# WRONG: Trying to optimize by caching nodes
node_cache = {}
for root_value in range(start, end + 1):
    if root_value not in node_cache:
        node_cache[root_value] = TreeNode(root_value)
    root_node = node_cache[root_value]  # Reusing the same node!
    root_node.left = left_subtree
    root_node.right = right_subtree

This causes multiple trees to share the same node objects, leading to corrupted tree structures where modifying one tree affects others.

Solution: Always create a new TreeNode instance for each tree:

# CORRECT: Create a new node for each tree
root_node = TreeNode(root_value, left_subtree, right_subtree)

3. Attempting Memoization Without Deep Copying

While memoization can optimize recursive solutions, applying it incorrectly here causes problems:

Wrong memoization:

memo = {}
def generate_trees_in_range(start, end):
    if (start, end) in memo:
        return memo[(start, end)]  # Returns references to existing trees!
  
    # ... generate trees ...
    memo[(start, end)] = result
    return result

This returns references to the same tree nodes, violating the requirement that each generated tree must be independent.

If memoization is needed: You would need to deep copy the entire tree structure, which negates most performance benefits:

import copy
if (start, end) in memo:
    return [copy.deepcopy(tree) for tree in memo[(start, end)]]

For this problem, it's better to avoid memoization entirely since we need unique tree instances.