LeetCode 95: Unique Binary Search Trees II Solution in Python Explained

Problem Statement

In LeetCode 95, you’re given an integer n. Your task is to return a list of all unique BSTs with exactly n nodes, numbered from 1 to n in any order, where each tree follows BST properties (left < root < right). This builds on traversal like LeetCode 94: Binary Tree Inorder Traversal, shifting focus to tree generation.

Constraints

• 1 <= n <= 8

Example

Let’s see some cases:

Copy codeInput: n = 3
Output: [
   [1,null,2,null,3],
   [1,null,3,2],
   [2,1,3],
   [3,1,null,null,2],
   [3,2,null,1]
]
Explanation: Five unique BSTs with nodes 1,2,3.

Copy codeInput: n = 1
Output: [[1]]
Explanation: Single node tree.

Copy codeInput: n = 2
Output: [[1,null,2],[2,1]]
Explanation: Two unique BSTs: 1->2, 2->1.

These examples show we’re generating all possible BSTs.

Understanding the Problem

How do you solve LeetCode 95: Unique Binary Search Trees II in Python? Take n = 3. We need five BSTs using 1,2,3, ensuring each is unique and valid (left < root < right). This isn’t a string task like LeetCode 93: Restore IP Addresses; it’s about constructing trees. We’ll use: 1. Recursive Construction: O(4ⁿ/√n) time, O(4ⁿ/√n) space—our best solution. 2. Dynamic Programming with Cloning: O(4ⁿ/√n) time, O(4ⁿ/√n) space—an alternative.

Let’s dive into the primary solution.

Solution 1: Recursive Construction Approach (Primary)

Explanation

Recursive Construction builds BSTs by picking each number as the root, recursively generating all left and right subtrees, and combining them. For each root i, use 1 to i-1 for the left and i+1 to n for the right. It’s the best solution due to its direct approach and alignment with BST properties, efficiently handling the combinatorial nature.

For n = 3:

• Root 1: Left [], Right [2,3].
• Root 2: Left [1], Right [3].
• Root 3: Left [1,2], Right [].

Step-by-Step Example

Assume a TreeNode class: class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val; self.left = left; self.right = right.

Example 1: n = 3

Goal: Return 5 unique BSTs.

• Start: Call generateTrees(1, 3).
• Step 1: Root = 1.
• Left: generateTrees(1, 0) → [].
• Right: generateTrees(2, 3) → [2,null,3], [3,2].
• Combine: [1,null,2,null,3], [1,null,3,2].
• Step 2: Root = 2.
• Left: generateTrees(1, 1) → [1].
• Right: generateTrees(3, 3) → [3].
• Combine: [2,1,3].
• Step 3: Root = 3.
• Left: generateTrees(1, 2) → [1,null,2], [2,1].
• Right: generateTrees(4, 3) → [].
• Combine: [3,1,null,null,2], [3,2,null,1].
• Finish: Return 5 trees.

Example 2: n = 1

Goal: Return [[1]].

• Start: generateTrees(1, 1).
• Step 1: Root = 1.
• Left: [], Right: [].
• Combine: [1].
• Finish: Return [[1]].

Example 3: n = 2

Goal: Return [[1,null,2],[2,1]].

• Start: generateTrees(1, 2).
• Step 1: Root = 1.
• Left: [], Right: [2].
• Combine: [1,null,2].
• Step 2: Root = 2.
• Left: [1], Right: [].
• Combine: [2,1].
• Finish: Return [[1,null,2],[2,1]].

How the Code Works (Recursive Construction) – Detailed Line-by-Line Explanation

Here’s the Python code with a thorough breakdown:

Copy codeclass TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def generateTrees(n: int) -> list[TreeNode]:
    # Line 1: Define helper function to generate trees in range
    def generate(start: int, end: int) -> list[TreeNode]:
        # start = first value, end = last value (e.g., 1, 3 for n=3)

        # Line 2: Base case - invalid range
        if start > end:
            # If start exceeds end (e.g., 1 > 0), no nodes to include
            return [None]
            # Returns [None] to allow combining with empty subtrees

        # Line 3: Initialize list for all possible trees
        trees = []
        # Stores all unique BSTs for this range (e.g., initially empty)

        # Line 4: Try each value as root
        for i in range(start, end + 1):
            # i loops from start to end (e.g., 1 to 3)
            # Each i becomes a potential root

            # Line 5: Generate all left subtrees
            left_trees = generate(start, i - 1)
            # Recursively gets all BSTs for values < i
            # e.g., i=1, generate(1, 0) → [None]

            # Line 6: Generate all right subtrees
            right_trees = generate(i + 1, end)
            # Recursively gets all BSTs for values > i
            # e.g., i=1, generate(2, 3) → [2,null,3], [3,2]

            # Line 7: Combine left and right subtrees
            for left in left_trees:
                # Iterates over each left subtree (e.g., [None])
                for right in right_trees:
                    # Iterates over each right subtree (e.g., [2,null,3], [3,2])

                    # Line 8: Create new tree with root i
                    root = TreeNode(i)
                    # New node with value i (e.g., 1)

                    # Line 9: Assign left subtree
                    root.left = left
                    # Sets left child (e.g., None for i=1)

                    # Line 10: Assign right subtree
                    root.right = right
                    # Sets right child (e.g., 2,null,3 for i=1)

                    # Line 11: Add tree to result
                    trees.append(root)
                    # Adds constructed tree (e.g., [1,null,2,null,3])

    # Line 12: Start construction from 1 to n
    return generate(1, n)
    # Initiates with full range (e.g., 1 to 3)
    # Returns list of all unique BSTs

This detailed breakdown clarifies how recursive construction generates all unique BSTs efficiently.

Alternative: Dynamic Programming with Cloning Approach

Explanation

Dynamic Programming with Cloning builds trees bottom-up, storing subtrees for each range and cloning them to avoid reference issues. For each range, try all roots, combining cloned left and right subtrees.

For n = 3:

• Build trees for lengths 1, 2, 3.
• Clone and shift values to form unique BSTs.

Step-by-Step Example (Alternative)

For n = 3:

• Length 1: [1], [2], [3].
• Length 2: [1,null,2], [2,1], etc.
• Length 3: Combine and shift, yielding 5 trees.

How the Code Works (DP with Cloning)

Copy codedef generateTreesDP(n: int) -> list[TreeNode]:
    def clone(node: TreeNode, offset: int) -> TreeNode:
        if not node:
            return None
        new_node = TreeNode(node.val + offset)
        new_node.left = clone(node.left, offset)
        new_node.right = clone(node.right, offset)
        return new_node

    dp = [[] for _ in range(n + 1)]
    dp[0] = [None]
    dp[1] = [TreeNode(1)]

    for length in range(2, n + 1):
        for root_val in range(1, length + 1):
            left_count = root_val - 1
            right_count = length - root_val
            for left in dp[left_count]:
                for right in dp[right_count]:
                    root = TreeNode(root_val)
                    root.left = clone(left, 0)
                    root.right = clone(right, left_count)
                    dp[length].append(root)

    return [clone(tree, 0) for tree in dp[n]]

Complexity

• Recursive Construction:
• Time: O(4ⁿ/√n) – Catalan number of BSTs.
• Space: O(4ⁿ/√n) – storing all trees.
• DP with Cloning:
• Time: O(4ⁿ/√n) – same number of trees.
• Space: O(4ⁿ/√n) – DP storage.

Efficiency Notes

Recursive Construction is the best solution with O(4ⁿ/√n) time and space, offering a direct, intuitive approach—DP with Cloning provides a structured alternative but requires cloning, adding complexity.

Key Insights

• BST Property: Left < root < right.
• Recursion: Breaks into subproblems.
• Uniqueness: All combinations covered.

Additional Example

For n = 4:

• Goal: 14 unique BSTs (Catalan number C(4)).
• Recursive: Builds trees systematically.

Edge Cases

• n = 1: [[1]].
• n = 2: [[1,null,2],[2,1]].
• n = 0: Not applicable (constraint n ≥ 1).

Both solutions handle these well.

Final Thoughts

LeetCode 95: Unique Binary Search Trees II in Python is a fascinating tree generation challenge. The Recursive Construction solution excels with its clarity and efficiency, while DP with Cloning offers a systematic alternative. Want more? Try LeetCode 96: Unique Binary Search Trees for counting BSTs or LeetCode 94: Binary Tree Inorder Traversal for traversal. Ready to practice? Solve LeetCode 95 on LeetCode with n = 3, aiming for 5 unique BSTs—test your skills now!