#95

Medium

auto_awesomeBinary-tree traversal and state tracking

LeetCode Problem Workspace

Unique Binary Search Trees II

Generate all structurally unique BSTs with values 1 to n using backtracking and recursive tree construction techniques.

dynamic programming backtracking tree binary search tree binary tree

Problem Statement

Given an integer n, construct all structurally unique binary search trees (BSTs) with nodes valued from 1 to n. Each BST must contain exactly n nodes, and each node must have a unique value. Return all valid BSTs in any order, ensuring that recursive combinations account for all possible left and right subtree arrangements.

This requires careful state tracking of each subtree during recursion. For example, with n = 3, all combinations of left and right children for each root must be explored. The challenge lies in combining subtrees without duplicating structures, applying a backtracking approach to systematically build each tree configuration and maintain valid BST properties. Examples illustrate the output format and tree structure combinations.

Examples

Example 1

Input: n = 3

Output: [[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3,2,null,1]]

Example details omitted.

Example 2

Input: n = 1

Output: [[1]]

Example details omitted.

Constraints

1 <= n <= 8

Solution Approach

Recursive Tree Generation

Select each integer from 1 to n as a potential root. For each root, recursively generate all possible left subtrees using values smaller than the root, and all possible right subtrees using values larger than the root. Combine each left and right subtree pair with the root to form all valid BSTs. This approach uses state tracking to ensure each subtree combination is explored exactly once.

Backtracking Integration

Backtracking ensures that after constructing left and right subtrees for a root, the recursion correctly returns to the previous state to try the next root value. By carefully managing recursion stacks and subtree lists, you avoid state contamination between different root selections. This prevents duplicate structures and ensures every unique BST configuration is generated efficiently.

Dynamic Programming Optimization

To improve efficiency, memoize results for subranges of values. Store all unique BSTs generated for a given start and end value. When the same subrange appears later, reuse the precomputed trees instead of recomputing. This reduces redundant recursion calls and leverages overlapping subproblems, aligning with dynamic programming principles while preserving correct BST generation.

Complexity Analysis

Metric	Value
Time	O(\dfrac{4^n}{\sqrt{n}})
Space	O(\sum_{k=1}^{n}\dfrac{4^k}{{\sqrt{k}}})

The time complexity is O(\frac{4^n}{\sqrt{n}}) due to Catalan number growth representing the number of unique BSTs, while space complexity is O(\sum_{k=1}^{n}\frac{4^k}{\sqrt{k}}) for storing all generated trees and recursive call stacks.

What Interviewers Usually Probe

Do you consider every integer as a potential root when generating BSTs?
Can you explain how backtracking ensures all unique subtree combinations are explored?
Will you optimize repeated subtree calculations with memoization for efficiency?

Common Pitfalls or Variants

Common pitfalls

Failing to combine all left and right subtree pairs for each root, leading to missing BSTs.
Not resetting recursive state between root selections, causing duplicate or incorrect tree structures.
Neglecting to memoize subtrees, resulting in exponential redundant computations and stack overflow for larger n.

Follow-up variants

Generate the number of unique BSTs (Unique Binary Search Trees I) instead of all structures.
Return all unique BSTs with a given pre-order traversal constraint.
Modify the BST generation to support duplicate values while maintaining valid BST rules.

FAQ

What is the best approach for generating all unique BSTs for n nodes?

Use recursive tree construction with backtracking to explore all left and right subtree combinations, ensuring each root selection covers every unique BST arrangement.

How does backtracking prevent duplicate trees in Unique Binary Search Trees II?

Backtracking restores previous recursion states after exploring a root's subtrees, preventing state contamination and ensuring each root produces all valid combinations independently.

Can dynamic programming optimize Unique Binary Search Trees II?

Yes, memoization stores previously computed subtrees for value ranges, reducing redundant recursion calls and improving efficiency while generating all unique BSTs.

What is the expected time and space complexity?

Time complexity is O(\frac{4^n}{\sqrt{n}}) due to Catalan number growth, and space complexity is O(\sum_{k=1}^{n}\frac{4^k}{\sqrt{k}}) for storing generated trees and recursion stack.

Are there common pitfalls when implementing Unique Binary Search Trees II?

Yes, common mistakes include not combining all left-right subtree pairs, failing to reset recursive state, and omitting memoization leading to redundant calculations.

terminal

Solution

Solution 1: DFS (Depth-First Search)

We design a function $dfs(i, j)$ that returns all feasible binary search trees composed of $[i, j]$, so the answer is $dfs(1, n)$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

# 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]]:
        def dfs(i: int, j: int) -> List[Optional[TreeNode]]:
            if i > j:
                return [None]
            ans = []
            for v in range(i, j + 1):
                left = dfs(i, v - 1)
                right = dfs(v + 1, j)
                for l in left:
                    for r in right:
                        ans.append(TreeNode(v, l, r))
            return ans

        return dfs(1, n)

Continue Practicing

#96 unique binary search trees #98 validate binary search tree #99 recover binary search tree