LeetCode 95 - Unique Binary Search Trees II

The problem asks us to generate all structurally unique binary search trees (BSTs) that contain exactly n nodes labeled from 1 to n.

leetcodemediumdynamic-programmingbacktrackingtreebinary-search-treebinary-tree

LeetCode Problem 95

Difficulty: 🟡 Medium
Topics: Dynamic Programming, Backtracking, Tree, Binary Search Tree, Binary Tree

Solution

Problem Understanding

The problem asks us to generate all structurally unique binary search trees (BSTs) that contain exactly n nodes labeled from 1 to n. A BST is a binary tree where for every node, all values in the left subtree are smaller than the node, and all values in the right subtree are larger. The input n is a single integer representing the number of nodes, and the output should be a list of all possible BSTs represented as root nodes of these trees.

The constraints indicate that n can range from 1 to 8. This means the total number of unique BSTs grows rapidly, but is manageable for backtracking or recursive generation techniques. Since the problem guarantees n >= 1, we do not need to handle negative numbers or zero.

Important edge cases include n = 1 (only one tree possible) and n = 2 (multiple small variations). Naive solutions may struggle due to combinatorial explosion if they attempt to generate all permutations without respecting BST properties.

Approaches

The brute-force approach would be to generate all permutations of numbers 1 to n and try to build a BST from each permutation, keeping only valid trees. While this produces correct results, it is extremely inefficient because most permutations do not correspond to unique BST structures, and the number of permutations is n!, which grows very fast.

The optimal approach leverages recursive generation and the BST property. For each number i from 1 to n, we treat i as the root. All numbers less than i form the left subtree, and all numbers greater than i form the right subtree. We recursively generate all possible left and right subtrees and combine them. This is essentially a form of divide and conquer, and ensures every tree generated is a valid BST. Memoization can be added to improve efficiency but is optional given the constraints.

Approach Time Complexity Space Complexity Notes
Brute Force O(n! * n) O(n!) Generate all permutations and filter valid BSTs. Very inefficient.
Optimal O(4^n / √n) O(4^n / √n) Recursive generation using BST properties. Catalan number of trees generated.

Algorithm Walkthrough

  1. Define a recursive function generate(start, end) that generates all unique BSTs with node values ranging from start to end.
  2. If start > end, return [None] because an empty subtree is a valid base case.
  3. Iterate through all values i from start to end. Treat i as the root.
  4. Recursively generate all left subtrees by calling generate(start, i - 1).
  5. Recursively generate all right subtrees by calling generate(i + 1, end).
  6. For each combination of left and right subtrees, create a new tree with root i, left child from left subtree, and right child from right subtree. Append this tree to the result list.
  7. Return the result list containing all trees generated for start to end.

Why it works: This approach works because it systematically considers every value as the root and generates all valid left and right subtrees independently, ensuring all combinations are captured. The recursion guarantees that each subtree is itself a valid BST.

Python Solution

from typing import List, Optional

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def generateTrees(self, n: int) -> List[Optional[TreeNode]]:
        if n == 0:
            return []
        
        def generate(start: int, end: int) -> List[Optional[TreeNode]]:
            if start > end:
                return [None]
            
            all_trees = []
            for i in range(start, end + 1):
                left_trees = generate(start, i - 1)
                right_trees = generate(i + 1, end)
                
                for l in left_trees:
                    for r in right_trees:
                        root = TreeNode(i)
                        root.left = l
                        root.right = r
                        all_trees.append(root)
            return all_trees
        
        return generate(1, n)

Explanation: The generateTrees function first handles n = 0 as a trivial edge case. The inner function generate(start, end) recursively produces all BSTs for the given range. We iterate through all possible roots, recursively compute left and right subtrees, and combine them. Each resulting tree is appended to the result list and returned.

Go Solution

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func generateTrees(n int) []*TreeNode {
    if n == 0 {
        return []*TreeNode{}
    }
    
    var generate func(start, end int) []*TreeNode
    generate = func(start, end int) []*TreeNode {
        if start > end {
            return []*TreeNode{nil}
        }
        var allTrees []*TreeNode
        for i := start; i <= end; i++ {
            leftTrees := generate(start, i-1)
            rightTrees := generate(i+1, end)
            for _, l := range leftTrees {
                for _, r := range rightTrees {
                    root := &TreeNode{Val: i, Left: l, Right: r}
                    allTrees = append(allTrees, root)
                }
            }
        }
        return allTrees
    }
    
    return generate(1, n)
}

Go-specific notes: The main difference is handling slices and nil pointers for empty subtrees. Slices are used instead of lists, and appending is explicit. Recursive structure is identical to the Python version.

Worked Examples

Example 1: n = 3

We call generate(1, 3):

  1. Root = 1, left = generate(1, 0) = [None], right = generate(2, 3) → produces trees [2,null,3] and [3,2,null].
  2. Root = 2, left = generate(1, 1) = [1], right = generate(3, 3) = [3] → produces tree [2,1,3].
  3. Root = 3, left = generate(1, 2) → [1,null,2] and [2,1,null], right = generate(4, 3) = [None].

All combinations yield 5 unique BSTs, matching the example output.

Example 2: n = 1

Only one root possible: 1, with left and right subtrees empty. Output is [1].

Complexity Analysis

Measure Complexity Explanation
Time O(4^n / √n) The number of unique BSTs for n nodes is the nth Catalan number, which is approximately 4^n / √n. Each tree construction is O(n) for copying nodes in recursive calls.
Space O(4^n / √n) Space is dominated by the number of BSTs stored and the recursion stack depth, which is O(n) per recursive call.

The Catalan number growth is typical for generating all unique BSTs, and it explains why recursive backtracking is feasible for small n but would be intractable for large n.

Test Cases

# test cases
sol = Solution()

# Example cases
assert len(sol.generateTrees(3)) == 5  # multiple unique BSTs
assert len(sol.generateTrees(1)) == 1  # single node

# Boundary and edge cases
assert sol.generateTrees(0) == []      # no nodes
assert len(sol.generateTrees(2)) == 2  # two-node trees

# Stress case
assert len(sol.generateTrees(4)) == 14 # Catalan number for n=4
assert len(sol.generateTrees(5)) == 42 # Catalan number for n=5
Test Why
n = 3 Validates multiple tree combinations
n = 1 Single node tree, minimal input
n = 0 Edge case with zero nodes
n = 2 Small multiple trees, checks basic recursion
n = 4,5 Stress test for Catalan number growth

Edge Cases

The first important edge case is n = 0. Although the problem states 1 <= n <= 8, a robust implementation may handle n = 0. The correct behavior is returning an empty list, representing no trees.

The second edge case is n = 1, which is trivial but tests the base case handling in recursion. The algorithm correctly returns a single node tree.

The third edge case is the maximum value n = 8. Here, the algorithm must generate 14, 42, up to 429 unique BSTs (Catalan numbers). Proper memory management and recursion depth handling are necessary. The recursive approach with explicit combination generation ensures all trees are created without duplication, satisfying constraints.

This implementation safely handles all edge cases by using empty lists to represent empty subtrees and correctly