⚡Flashcard Drill➔
NeetCode #447LC-96MediumTrees
← Back to All Problems

#447 · #96 · Unique Binary Search Trees(不同的二叉搜索树)

📌 Problem Statement & Constraints

Given an integer n, return the number of structurally unique binary search trees that store exactly n distinct values. Constraints: 1 <= n <= 19.

💡 Core Algorithmic Approaches

  1. Fix the root: if it holds the j-th smallest value, the left subtree has j values and the right has n - 1 - j.
  2. The subtrees are independent, so the count is sum over j of dp[j] * dp[n-1-j].
  3. This is the Catalan number recurrence, and it is exactly what Unique Binary Search Trees II enumerates.
  4. The DP is O(n^2) time and O(n) space, versus the closed form which needs big-number division.

💻 Benchmark Python3 Implementation

class Solution:
    def numTrees(self, n: int) -> int:
        dp = [0] * (n + 1)
        dp[0] = 1                          # the empty tree
        for i in range(1, n + 1):
            for j in range(i):
                # j nodes on the left, i - 1 - j on the right
                dp[i] += dp[j] * dp[i - 1 - j]
        return dp[n]

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n^2): the double loop over the root choice and the tree size.
💾 Space Complexity
O(n) for the DP array.

⚠️ Interview Pitfalls & Follow-ups

  • Forgetting dp[0] = 1: the recurrence would produce all zeros, since the empty subtree is a valid (and necessary) base case.
  • Using dp[i-1-j] incorrectly: the right subtree has i - 1 - j nodes, where j is the left subtree size.
  • Returning a float: the closed form C(2n, n) / (n + 1) involves division; the DP stays integral.
  • Confusing this with counting binary trees: the BST structure is determined by the values' order, so the shapes are what is being counted.
⚡
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