/95. Generate All Unique Binary Search Trees

95. Generate All Unique Binary Search Trees

Medium

Dynamic Programming62.1% acceptance

Given an integer node_count, generate all structurally unique binary search trees (BSTs) containing node_count nodes with unique values from 1 to node_count. Return a list of all possible BSTs, where each tree is represented by its root node. The order of the trees in the output does not matter.

Example 1

Input: 2

Output: [TreeNode(1, None, TreeNode(2)), TreeNode(2, TreeNode(1), None)]

Explanation: There are two unique BSTs for node_count=2: one with 1 as root and 2 as right child, and one with 2 as root and 1 as left child.

Example 2

Input: 4

Output: A list of 14 unique BST root nodes (structure omitted for brevity)

Explanation: There are 14 unique BSTs for node_count=4, each using values 1 to 4.

Constraints

1 <= node_count <= 8
Each BST must use all values from 1 to node_count exactly once
Return all structurally unique BSTs

Python (current runtime)

Case 1

Input: 3

Expected: A list of 5 unique BST root nodes (structure omitted for brevity)

Case 2

Input: 1

Expected: [TreeNode(1)]