⚡Flashcard Drill➔
NeetCode #448LC-95MediumTrees
← Back to All Problems

#448 · #95 · Unique Binary Search Trees II(不同的二叉搜索树 II)

📌 Problem Statement & Constraints

Given an integer n, return all structurally unique binary search trees that store the values 1..n. Return the roots in any order. Constraints: 1 <= n <= 8.

💡 Core Algorithmic Approaches

  1. Recursively build all trees over a value range [lo, hi].
  2. For each candidate root value v, combine every left tree over [lo, v-1] with every right tree over [v+1, hi].
  3. The base case lo > hi returns a single None, representing an empty subtree.
  4. The total output is the Catalan number, which is why n is capped at 8.

💻 Benchmark Python3 Implementation

class Solution:
    def generateTrees(self, n: int) -> List[Optional[TreeNode]]:
        def build(lo: int, hi: int) -> List[Optional[TreeNode]]:
            if lo > hi:
                return [None]              # one empty subtree
            res = []
            for v in range(lo, hi + 1):    # v is the root value
                for l in build(lo, v - 1):
                    for r in build(v + 1, hi):
                        res.append(TreeNode(v, l, r))
            return res

        return build(1, n) if n else []


# Memoised variant: reuse the trees for each (lo, hi) range
class Solution2:
    def generateTrees(self, n: int) -> List[Optional[TreeNode]]:
        from functools import lru_cache

        @lru_cache(maxsize=None)
        def build(lo: int, hi: int):
            if lo > hi:
                return (None,)
            res = []
            for v in range(lo, hi + 1):
                for l in build(lo, v - 1):
                    for r in build(v + 1, hi):
                        res.append(TreeNode(v, l, r))
            return tuple(res)

        return list(build(1, n)) if n else []

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n * Catalan(n)): each generated tree requires O(n) node creations.
💾 Space Complexity
O(Catalan(n)) for the output, plus O(n) recursion depth.

⚠️ Interview Pitfalls & Follow-ups

  • Returning [] for the empty range instead of [None]: then no tree would ever be built, since the loops iterate over the child lists.
  • Reusing the same subtree objects across different trees: the memoised variant shares nodes, which mutates shared structure if the caller modifies the trees -- acceptable for this problem but worth noting.
  • Trying to deduplicate structurally identical trees: distinct root values always give distinct BSTs, so no deduplication is needed.
  • Using a value range based on 0: the values are 1..n.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Trees Problems