Unique Binary Search Trees II

Medium · Trees · Explanation and code example

Dynamic Programming (Space Optimized)

How it works

The number of unique BST structures depends only on the count of nodes, not their actual values. We can generate all BST structures for sizes 0, 1, 2, ..., n and then adjust node values using a shift function. For a tree structure with nodes 1 to k, we can create a tree with nodes offset+1 to offset+k by adding offset to each node's value.

Steps

  1. Create an array dp[length] to store all BST structures for trees with length nodes.
  2. Initialize dp[0] = [null] (empty tree).
  3. For each length from 1 to n:
    • For each root position val from 1 to length:
      • Left subtree has val - 1 nodes (from dp[val-1]).
      • Right subtree has length - val nodes (from dp[length-val]), but needs value shifting.
      • Create trees by combining leftTree from dp[val-1] with shift(rightTree, val) from dp[length-val].
  4. Define a shift(node, offset) function that creates a new tree with all values increased by offset.
  5. Return dp[n].

Complexity

  • Time complexity: O(frac {4 ^ n}{sqrt {n}})
  • Space complexity:
    • O(n) for the recursion stack.
    • O(n) extra space.
    • O(frac {4 ^ n}{sqrt {n}}) space for the output.

Things to watch for

Returning Empty List Instead of List with Null

When the range is invalid (left > right), the base case should return a list containing null (representing an empty subtree), not an empty list. Returning an empty list causes the nested loops to skip all combinations, producing no trees at all.

Reusing Tree Nodes Across Different Trees

In the space-optimized approach, left subtrees are shared across multiple result trees since they have identical structure and values. However, right subtrees need to be cloned with shifted values. Forgetting to create new nodes when shifting values causes all trees to share and mutate the same nodes incorrectly.

Incorrect Value Shifting for Right Subtrees

When using the space-optimized DP approach, right subtree values must be shifted by the root value. A common mistake is applying the wrong offset or forgetting to recursively shift all nodes in the subtree. Each node in the right subtree should have offset added to its value.

Python code example

from typing import 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]]:
        dp = [[] for _ in range(n + 1)]
        dp[0] = [None]

        for length in range(1, n + 1):
            dp[length] = []
            for val in range(1, length + 1):
                for leftTree in dp[val - 1]:
                    for rightTree in dp[length - val]:
                        root = TreeNode(val)
                        root.left = leftTree
                        root.right = self.shift(rightTree, val)
                        dp[length].append(root)

        return dp[n]

    def shift(self, node: Optional[TreeNode], offset: int) -> Optional[TreeNode]:
        if not node:
            return None
        root = TreeNode(node.val + offset)
        root.left = self.shift(node.left, offset)
        root.right = self.shift(node.right, offset)
        return root

C++ code example

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<TreeNode*> generateTrees(int n) {
        vector<vector<TreeNode*>> dp(n + 1);
        dp[0].push_back(nullptr);

        for (int length = 1; length <= n; length++) {
            for (int val = 1; val <= length; val++) {
                for (auto& leftTree : dp[val - 1]) {
                    for (auto& rightTree : dp[length - val]) {
                        TreeNode* root = new TreeNode(val);
                        root->left = leftTree;
                        root->right = shift(rightTree, val);
                        dp[length].push_back(root);
                    }
                }
            }
        }
        return dp[n];
    }

private:
    TreeNode* shift(TreeNode* node, int offset) {
        if (!node) return nullptr;
        TreeNode* root = new TreeNode(node->val + offset);
        root->left = shift(node->left, offset);
        root->right = shift(node->right, offset);
        return root;
    }
};
Source and license

Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.

Check the explanation on LeetCode Watch NeetCode on YouTube

Your recall check is in progress. Write your attempt before revealing the explanation.

Resume recall check

Browse all problem explanations