Domain 2MediumCORE

Unique Binary Search Trees

We are given an integer n representing the number of nodes with unique values from 1 to n. We need to count how many structurally distinct Binary Search Trees (BSTs) can be formed using these specific node counts and value ranges.

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Dynamic Programming#Tree

96. Unique Binary Search Trees

Model: qwen3.5:9b
Topics: Dynamic Programming,Tree
FAANG asked: 0
Acceptance rate: 54.7%


Problem Breakdown

We are given an integer n representing the number of nodes with unique values from 1 to n. We need to count how many structurally distinct Binary Search Trees (BSTs) can be formed using these specific node counts and value ranges.

Key constraints:

  • Values must strictly follow BST properties (left child < root, right child > root).
  • Since the input is a range [1..n][1..n], any subset of size k will form trees structurally identical to those for nodes 0..k0..k or 1..k1..k. The actual values don’t change the count, only the structure matters.
  • We must return an integer representing this count. Given Python’s arbitrary precision integers, overflow isn’t a concern like in C++/Java, but we should still be mindful of growth rates (Catalan numbers grow exponentially).

Intuition

A brute-force approach would try to generate every possible tree structure and validate BST properties, which is O(n!)O(n!) or worse. That’s too slow for even moderate n.

Instead, let’s think recursively about the root node. If we pick a specific value as the root (say, index i from 1 to n), then:

  • All nodes smaller than i must go into the left subtree.
  • All nodes larger than i must go into the right subtree.

Crucially, once we fix the size of the left and right subtrees, their specific values don’t matter for the count—only how many ways to arrange them matters. This means if there are LL unique trees possible for a left side with k nodes, and RR unique trees for a right side with m nodes, then combining any one of those structures gives us valid BSTs: Total = L×RL \times R.

Since we need to solve this for all sizes from 1 up to n, the subproblems overlap. This signals Dynamic Programming (DP). We can build our solution bottom-up by solving for smaller tree counts first and using them to compute larger ones.

Approach

We will use an iterative DP approach with a table dp where dp[i] stores the number of unique BSTs that have exactly i nodes.

  1. Base Case: A tree with 0 nodes (empty) is structurally valid in one way, so we initialize dp[0] = 1.
  2. Iteration: We iterate through every possible total node count j from 1 to n. For each j, we treat it as the current problem size and try every possible root position i (from 1 to j).
  3. Calculation: If i is the root, there are (i-1) nodes in the left subtree and (j-i) nodes in the right subtree. The number of ways for this specific root configuration is dp[i-1] * dp[j-i].
  4. Accumulate: We sum these products over all possible roots to get dp[j].
  5. Result: After filling up to index n, return dp[n].

Complexity Analysis

  • Time Complexity: O(n2)O(n^2). The outer loop runs from 1 to n, and the inner summation (root iteration) runs proportional to the current size of the tree. This sums to ∑i=1ni≈O(n2)\sum_{i=1}^{n} i \approx O(n^2).
  • Space Complexity: O(n)O(n). We use a single array dp of size n + 1.

Solution

class Solution:
    def numTrees(self, n: int) -> int:
        # dp[i] will store the number of unique BSTs with i nodes.
        # Initialize base case: an empty tree (0 nodes) is structurally valid once.
        dp = [1] * (n + 1) 
        
        # Iterate through each size from 2 to n to compute counts for larger trees
        for j in range(2, n + 1):
            # Try every possible root position i within the current tree of size j
            # Left subtree has nodes: [0...i-1] -> count is dp[i-1] (using index logic)
            # Right subtree has nodes: [i+1...j] -> count is dp[j-i] 
            for left_nodes in range(j):
                right_nodes = j - 1 - left_nodes
                dp[j] += dp[left_nodes + 1] * dp[right_nodes + 1]

        return dp[n]

Correction during implementation: The logic above uses left_nodes as count directly. Let’s refine the loop for clarity in code to match standard DP indexing where we iterate root index or left subtree size explicitly.

Refined Logic: For a tree of size j, let i be the number of nodes in the left subtree (ranging from 0 to j-1). The right subtree will then have j - 1 - i nodes. The recurrence is dp[j] += dp[i] * dp[j - 1 - i].

class Solution:
    def numTrees(self, n: int) -> int:
        # Initialize DP array where index represents number of nodes.
        # Base case: A tree with 0 nodes is structurally valid (empty).
        dp = [1] * (n + 1) 
        
        # Compute for each size from 2 up to n
        for j in range(2, n + 1):
            # Iterate through all possible sizes of the left subtree.
            # If we have 'j' nodes total and pick a root:
            # Left side has i nodes (0 <= i < j)
            # Right side has (j - 1 - i) nodes
            for i in range(j): 
                dp[j] += dp[i] * dp[j - 1 - i]
                
        return dp[n]

Edge Cases Handled

  • n = 1: The loop range(2, n+1) will not execute if n=1, returning the pre-initialized value at index 1 which is implicitly handled by initialization [1]*(n+1). Wait, standard init sets all to 1. If we run logic for j=1?
    • Actually, with dp = [0] * (n + 1) and setting dp[0]=1, then loop starts at 2 is wrong because index 1 needs calculation or initialization.
    • Better: Initialize dp as [0]*(n+1). Set dp[0]=1, dp[1]=1. Loop from 2 to n.
    • Wait, if I initialize with all zeros and set base cases explicitly? Or just use the math that works for j=1 naturally?
    • If loop starts at 2: For n=1, returns dp[1] which is initialized as 0 in [0]*(...). That’s wrong.
    • Correction: Initialize with zeros, set dp[0]=1. Loop for j from 1 to n? If j=1, inner loop range(1) -> i=0. Right = 1-1-0 = 0. dp[1] += dp[0]dp[0] = 11 = 1. Correct.
    • So I will initialize dp with zeros and set dp[0]=1, then loop from 2 to n? No, if n=1 we need result 1.
    • Let’s stick to the cleanest logic: Initialize array of size n+1. Set dp[0] = 1. Loop j from 1 to n. Inner loop i (left nodes) from 0 to j-1.
    • Wait, if I use [1]*(n+1) it implies all are 1. That’s wrong for j>1 initially.
    • Correct approach: Initialize with zeros or handle base cases carefully. Let’s write the code block cleanly in the final output to ensure correctness without over-explaining implementation details that might confuse the reader, but ensuring logic holds.

Revised Code Plan: Initialize dp of size n+1. Set dp[0] = 1. Loop j from 2 to n? No, if we want to handle j=1 correctly inside loop: Actually, the standard Catalan DP usually starts with dp array initialized. If I initialize all zeros and set dp[0]=1, then for j=1 (if included in outer loop), it calculates correctly as dp[0]*dp[0]. However, to be safe against n=1 constraint: If n is input 1, we return 1. Let’s use the standard pattern where dp[i] accumulates sums.

Final Code Logic for Solution section:

class Solution:
    def numTrees(self, n: int) -> int:
        dp = [0] * (n + 1)
        dp[0] = 1
        
        # Iterate through tree sizes from 2 to n. 
        # Note: If we loop j=1..n and inner i=0..j-1, it works for all cases including n=1 if initialized correctly.
        # However, usually people skip j=1 because dp[1] is naturally handled or set manually.
        # Let's iterate 2 to n as per standard optimization since dp[1]=1 is known base case? 
        # No, let's just loop from 2 to n and handle initialization carefully for edge cases like n=1.
        
        if n == 0: return 0 
        
        # Actually simplest logic that covers all constraints cleanly:
        dp = [0] * (n + 1)
        dp[0] = 1
        
        for j in range(2, n + 1): 
            # This skips calculating dp[1]. We must ensure dp[1]=1.
            pass 
        
        return dp[n]

Let’s just write the robust version: Initialize dp with zeros except index 0 is 1. Loop from 2 to n? If input is 1, loop doesn’t run, returns dp[1]. But dp[1] would be 0 if initialized as [0]*(n+1). So I must initialize dp = [1] * (n + 1) and then overwrite with zeros or just handle the logic such that it works. Actually, standard solution:

        dp = [0] * (n + 1)
        dp[0] = 1
        
        for j in range(2, n + 1): # Calculates sizes >= 2
             ... 
        return dp[n] if n > 1 else 1

Wait, simpler: Just loop j from 1 to n. If j=1, inner loop runs once (i=0), calculates dp[1] += dp[0]*dp[0] = 1. So I will iterate range(2, n + 1) but ensure dp[1]=1 is set or handled. Actually, the cleanest way: Initialize dp with zeros. Set dp[0]=1. Loop j from 2 to n. If n=1, return 1 immediately? Or just let loop handle it if I start at 1? If I start outer loop at 1, then for n=1: j=1 runs once. dp[1] becomes 1. Correct. So Outer Loop range(2, …) is optimization but requires manual base case dp[1]=1. I will use the optimized version (start from 2) and manually set dp array initialization to handle n=1 gracefully or just iterate starting at 1 for simplicity in explanation? Iterating from 2 is standard because dp[0] handles empty, dp[1] is trivially 1. Let’s stick to the most robust code: Initialize with zeros, set dp[0]=1. Loop j from 2 to n. If n=1 return 1 (or handle via logic). Actually, if I initialize dp = [1]*(n+1) and then run loop starting at 2? No that assumes all are 1 initially which is wrong for accumulation. Okay, final decision: Initialize with zeros. Set dp[0]=1. Loop j from 2 to n. If n=1 return 1 explicitly or ensure logic covers it. Actually, simplest code without special casing n==1:

        dp = [0] * (n + 1)
        dp[0] = 1
        
        for i in range(1, n + 1): # Calculate size 'i' using previous results
            for j in range(i):    # Left subtree has j nodes
                right_nodes = i - 1 - j
                dp[i] += dp[j] * dp[right_nodes]

If n=1: dp[0]=1. Loop i from 1 to 1. Inner loop j range(1) -> 0. Right nodes = 0. dp[1] += dp[0]*dp[0] (1*1). Returns 1. This is cleanest and handles n=1 naturally without special if-statements.

Edge Cases Handled

  • n = 1: The loops execute once, calculating the single node tree correctly as dp[0] * dp[0].
  • Large Output Values (Catalan Growth): Python integers handle arbitrary size automatically; no overflow handling needed beyond standard logic.
  • Empty Tree Logic (n=0): While constraints say 1≤n1 \le n, the code relies on dp[0]=1, which correctly represents an empty tree in the recurrence relation, ensuring mathematical consistency even if inputs were extended to 0 (though not required by LeetCode).