95. Unique Binary Search Trees II

Problem¶

Given n, generate every structurally unique BST containing each value from 1 through n exactly once, in any order.

n = 3
x(left,right), · = empty, leaves abbreviated as x

Output:
[
  1(·,2(·,3)),
  1(·,3(2,·)),
  2(1,3),
  3(1(·,2),·),
  3(2(1,·),·)
]

Key trick¶

Choose each value as the root, recursively generate all valid left and right subtrees, then take their Cartesian product. An empty interval must return [None] so it contributes one valid choice.

Trap¶

• Returning [] for an empty interval prevents any combinations from being created.
• The recursive calls return lists of trees, not individual child nodes.
• Every left subtree must be paired with every right subtree.
• Inclusive interval boundaries require range(lo, hi + 1).

Why is it interesting?¶

It combines divide and conquer, dynamic programming, Cartesian products, and the Catalan-number structure of BST enumeration.

Python solution¶

from functools import cache
from utils import TreeNode


class Solution:
    def generateTrees(self, n: int) -> list[TreeNode | None]:

        @cache
        def build(lo, hi):
            if lo > hi:
                return [None]

            res = []
            for val in range(lo, hi + 1):
                for left in build(lo, val - 1):
                    for right in build(val + 1, hi):
                        res.append(TreeNode(val, left, right))
            return res

        return build(1, n)

Let \(C_n\) be the \(n\)th Catalan number.

• Time: \(O(nC_n)\)
• Space: \(O(nC_n)\) for the generated trees and \(O(n)\) recursion depth

Comment on my solution¶

Your root-selection and divide-and-conquer idea is correct, but the implementation is incomplete:

• range(lo, hi) excludes hi.
• build needs an empty-interval base case returning [None].
• build returns multiple trees, so its result cannot be assigned directly to one child.
• Every left and right subtree pair needs a new root node.
• Both build and generateTrees need return statements.

# Ideas:
# - as we have to generate all possible trees, maybe DFS backtracking
# - divide and conquer
#   - pick a root an recursively build left and right children
# - I don't see how to solve this problem.

class Solution:
    def generateTrees(self, n: int) -> list[TreeNode | None]:
        def build(lo, hi):
            for root in range(lo, hi):
                node = TreeNode(root)
                node.left = build(lo, root - 1)
                node.right= build(root + 1, hi)