95. Unique Binary Search Trees II - Explanation

Description

Return the roots of all structurally distinct binary search trees that contain each value from 1 through n exactly once.

In a binary search tree, every value in a node's left subtree is smaller than the node's value, and every value in its right subtree is larger. Trees with different left/right arrangements are distinct.

Return every valid tree exactly once, in any order. The examples show each tree in level order, using null for missing children and omitting trailing nulls.

Example 1:

Unique Binary Search Trees II, example 1: illustration of the example

Input: n = 1

Output: [[1]]

Explanation: With only value 1, the only valid tree is a single node.

Example 2:

Unique Binary Search Trees II, example 2: illustration of the example

Input: n = 2

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

Explanation: Either value can be the root. Root 1 must have right child 2; root 2 must have left child 1. These are the only two structures.

Example 3:

Unique Binary Search Trees II, example 3: illustration of the example

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]
]

Explanation: Root 1 permits two arrangements of values 2 and 3 on its right. Root 2 has left child 1 and right child 3. Root 3 permits two arrangements on its left, giving five distinct trees.

Constraints:

1 <= n <= 8

Topics

Company Tags

Please upgrade to NeetCode Pro to view company tags.

Prerequisites

Before attempting this problem, you should be comfortable with:

Binary Search Tree Properties - Understanding that left subtree values are smaller and right subtree values are larger than the root
Recursion - Building solutions by combining results from recursive subproblems
Dynamic Programming - Using memoization to cache and reuse previously computed subtrees
Tree Construction - Creating and linking tree nodes to build complete tree structures

1. Recursion

Intuition

To generate all unique BSTs with values from 1 to n, we pick each value as the root and recursively generate all possible left and right subtrees. When val is the root, values 1 to val-1 form the left subtree and values val+1 to n form the right subtree. We combine every leftTree with every rightTree to create all unique trees with that root.

Algorithm

Define a recursive function generate(left, right) that returns a list of all unique BSTs using values from left to right.
Base case: If left > right, return a list containing null (representing an empty subtree).
For each value val from left to right:
- Recursively generate all left subtrees using generate(left, val - 1).
- Recursively generate all right subtrees using generate(val + 1, right).
- For each combination of leftTree and rightTree, create a new tree with val as root and add it to res.
Return res.
Call generate(1, n) to get the final result.

# 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 generate(left, right):
            if left > right:
                return [None]

            res = []
            for val in range(left, right + 1):
                for leftTree in generate(left, val - 1):
                    for rightTree in generate(val + 1, right):
                        root = TreeNode(val, leftTree, rightTree)
                        res.append(root)
            return res

        return generate(1, n)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    public List<TreeNode> generateTrees(int n) {
        return generate(1, n);
    }

    private List<TreeNode> generate(int left, int right) {
        List<TreeNode> res = new ArrayList<>();
        if (left > right) {
            res.add(null);
            return res;
        }

        for (int val = left; val <= right; val++) {
            List<TreeNode> leftTrees = generate(left, val - 1);
            List<TreeNode> rightTrees = generate(val + 1, right);

            for (TreeNode leftTree : leftTrees) {
                for (TreeNode rightTree : rightTrees) {
                    res.add(new TreeNode(val, leftTree, rightTree));
                }
            }
        }
        return res;
    }
}

/**
 * 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) {
        return generate(1, n);
    }

private:
    vector<TreeNode*> generate(int left, int right) {
        if (left > right) return {nullptr};

        vector<TreeNode*> res;
        for (int val = left; val <= right; val++) {
            vector<TreeNode*> leftTrees = generate(left, val - 1);
            vector<TreeNode*> rightTrees = generate(val + 1, right);

            for (auto& leftTree : leftTrees) {
                for (auto& rightTree : rightTrees) {
                    res.push_back(new TreeNode(val, leftTree, rightTree));
                }
            }
        }
        return res;
    }
};

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     constructor(val = 0, left = null, right = null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    /**
     * @param {number} n
     * @return {TreeNode[]}
     */
    generateTrees(n) {
        const generate = (left, right) => {
            if (left > right) return [null];

            let res = [];
            for (let val = left; val <= right; val++) {
                let leftTrees = generate(left, val - 1);
                let rightTrees = generate(val + 1, right);

                for (let leftTree of leftTrees) {
                    for (let rightTree of rightTrees) {
                        res.push(new TreeNode(val, leftTree, rightTree));
                    }
                }
            }
            return res;
        };

        return generate(1, n);
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    public IList<TreeNode> GenerateTrees(int n) {
        return Generate(1, n);
    }

    private IList<TreeNode> Generate(int left, int right) {
        var res = new List<TreeNode>();
        if (left > right) {
            res.Add(null);
            return res;
        }

        for (int val = left; val <= right; val++) {
            var leftTrees = Generate(left, val - 1);
            var rightTrees = Generate(val + 1, right);

            foreach (var leftTree in leftTrees) {
                foreach (var rightTree in rightTrees) {
                    res.Add(new TreeNode(val, leftTree, rightTree));
                }
            }
        }
        return res;
    }
}

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func generateTrees(n int) []*TreeNode {
    var generate func(left, right int) []*TreeNode
    generate = func(left, right int) []*TreeNode {
        if left > right {
            return []*TreeNode{nil}
        }

        var res []*TreeNode
        for val := left; val <= right; val++ {
            leftTrees := generate(left, val-1)
            rightTrees := generate(val+1, right)

            for _, leftTree := range leftTrees {
                for _, rightTree := range rightTrees {
                    res = append(res, &TreeNode{val, leftTree, rightTree})
                }
            }
        }
        return res
    }
    return generate(1, n)
}

/**
 * Example:
 * var ti = TreeNode(5)
 * var v = ti.`val`
 * Definition for a binary tree node.
 * class TreeNode(var `val`: Int) {
 *     var left: TreeNode? = null
 *     var right: TreeNode? = null
 * }
 */
class Solution {
    fun generateTrees(n: Int): List<TreeNode?> {
        fun generate(left: Int, right: Int): List<TreeNode?> {
            if (left > right) return listOf(null)

            val res = mutableListOf<TreeNode?>()
            for (v in left..right) {
                val leftTrees = generate(left, v - 1)
                val rightTrees = generate(v + 1, right)

                for (leftTree in leftTrees) {
                    for (rightTree in rightTrees) {
                        res.add(TreeNode(v).apply {
                            this.left = leftTree
                            this.right = rightTree
                        })
                    }
                }
            }
            return res
        }
        return generate(1, n)
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public var val: Int
 *     public var left: TreeNode?
 *     public var right: TreeNode?
 *     public init() { self.val = 0; self.left = nil; self.right = nil; }
 *     public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
 *     public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
 *         self.val = val
 *         self.left = left
 *         self.right = right
 *     }
 * }
 */
class Solution {
    func generateTrees(_ n: Int) -> [TreeNode?] {
        func generate(_ left: Int, _ right: Int) -> [TreeNode?] {
            if left > right {
                return [nil]
            }

            var res = [TreeNode?]()
            for val in left...right {
                let leftTrees = generate(left, val - 1)
                let rightTrees = generate(val + 1, right)

                for leftTree in leftTrees {
                    for rightTree in rightTrees {
                        res.append(TreeNode(val, leftTree, rightTree))
                    }
                }
            }
            return res
        }
        return generate(1, n)
    }
}

impl Solution {
    pub fn generate_trees(n: i32) -> Vec<Option<Rc<RefCell<TreeNode>>>> {
        fn generate(left: i32, right: i32) -> Vec<Option<Rc<RefCell<TreeNode>>>> {
            if left > right {
                return vec![None];
            }
            let mut res = vec![];
            for val in left..=right {
                let left_trees = generate(left, val - 1);
                let right_trees = generate(val + 1, right);
                for lt in &left_trees {
                    for rt in &right_trees {
                        res.push(Some(Rc::new(RefCell::new(TreeNode {
                            val,
                            left: lt.clone(),
                            right: rt.clone(),
                        }))));
                    }
                }
            }
            res
        }
        generate(1, n)
    }
}

Time & Space Complexity

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

2. Dynamic Programming (Top-Down)

Intuition

The recursive solution recomputes the same ranges multiple times. For example, generate(2, 4) might be called from different parent recursions. We can cache results for each (left, right) pair to avoid regenerating the same subtrees.

Algorithm

Create a 2D memoization table dp to store results for each (left, right) pair.
Define a recursive function generate(left, right) similar to the basic recursive approach.
Before computing, check if dp[left][right] already has a value. If so, return the cached list.
Compute all trees for the range and store res in dp[left][right].
Return generate(1, n).

# 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 = {}

        def generate(left, right):
            if left > right:
                return [None]
            if (left, right) in dp:
                return dp[(left, right)]

            res = []
            for val in range(left, right + 1):
                for leftTree in generate(left, val - 1):
                    for rightTree in generate(val + 1, right):
                        root = TreeNode(val, leftTree, rightTree)
                        res.append(root)

            dp[(left, right)] = res
            return res

        return generate(1, n)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    private List<TreeNode>[][] dp;

    public List<TreeNode> generateTrees(int n) {
        dp = new ArrayList[n + 1][n + 1];
        return generate(1, n);
    }

    private List<TreeNode> generate(int left, int right) {
        if (left > right) return Collections.singletonList(null);
        if (dp[left][right] != null) return dp[left][right];

        List<TreeNode> res = new ArrayList<>();
        for (int val = left; val <= right; val++) {
            for (TreeNode leftTree : generate(left, val - 1)) {
                for (TreeNode rightTree : generate(val + 1, right)) {
                    res.add(new TreeNode(val, leftTree, rightTree));
                }
            }
        }
        return dp[left][right] = res;
    }
}

/**
 * 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<vector<vector<TreeNode*>>> dp;

    vector<TreeNode*> generateTrees(int n) {
        dp.resize(n + 1, vector<vector<TreeNode*>>(n + 1));
        return generate(1, n);
    }

private:
    vector<TreeNode*> generate(int left, int right) {
        if (left > right) return {nullptr};
        if (!dp[left][right].empty()) return dp[left][right];

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

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     constructor(val = 0, left = null, right = null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    /**
     * @param {number} n
     * @return {TreeNode[]}
     */
    generateTrees(n) {
        const dp = Array.from({ length: n + 1 }, () => Array(n + 1).fill(null));

        const generate = (left, right) => {
            if (left > right) return [null];
            if (dp[left][right]) return dp[left][right];

            let res = [];
            for (let val = left; val <= right; val++) {
                for (let leftTree of generate(left, val - 1)) {
                    for (let rightTree of generate(val + 1, right)) {
                        res.push(new TreeNode(val, leftTree, rightTree));
                    }
                }
            }
            return (dp[left][right] = res);
        };

        return generate(1, n);
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    private IList<TreeNode>[][] dp;

    public IList<TreeNode> GenerateTrees(int n) {
        dp = new IList<TreeNode>[n + 1][];
        for (int i = 0; i <= n; i++) {
            dp[i] = new IList<TreeNode>[n + 1];
        }
        return Generate(1, n);
    }

    private IList<TreeNode> Generate(int left, int right) {
        if (left > right) return new List<TreeNode> { null };
        if (dp[left][right] != null) return dp[left][right];

        var res = new List<TreeNode>();
        for (int val = left; val <= right; val++) {
            foreach (var leftTree in Generate(left, val - 1)) {
                foreach (var rightTree in Generate(val + 1, right)) {
                    res.Add(new TreeNode(val, leftTree, rightTree));
                }
            }
        }
        return dp[left][right] = res;
    }
}

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func generateTrees(n int) []*TreeNode {
    dp := make([][][]*TreeNode, n+1)
    for i := range dp {
        dp[i] = make([][]*TreeNode, n+1)
    }

    var generate func(left, right int) []*TreeNode
    generate = func(left, right int) []*TreeNode {
        if left > right {
            return []*TreeNode{nil}
        }
        if dp[left][right] != nil {
            return dp[left][right]
        }

        var res []*TreeNode
        for val := left; val <= right; val++ {
            for _, leftTree := range generate(left, val-1) {
                for _, rightTree := range generate(val+1, right) {
                    res = append(res, &TreeNode{val, leftTree, rightTree})
                }
            }
        }
        dp[left][right] = res
        return res
    }
    return generate(1, n)
}

/**
 * Example:
 * var ti = TreeNode(5)
 * var v = ti.`val`
 * Definition for a binary tree node.
 * class TreeNode(var `val`: Int) {
 *     var left: TreeNode? = null
 *     var right: TreeNode? = null
 * }
 */
class Solution {
    fun generateTrees(n: Int): List<TreeNode?> {
        val dp = Array<Array<List<TreeNode?>?>>(n + 1) { arrayOfNulls(n + 1) }

        fun generate(left: Int, right: Int): List<TreeNode?> {
            if (left > right) return listOf(null)
            dp[left][right]?.let { return it }

            val res = mutableListOf<TreeNode?>()
            for (v in left..right) {
                for (leftTree in generate(left, v - 1)) {
                    for (rightTree in generate(v + 1, right)) {
                        res.add(TreeNode(v).apply {
                            this.left = leftTree
                            this.right = rightTree
                        })
                    }
                }
            }
            dp[left][right] = res
            return res
        }
        return generate(1, n)
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public var val: Int
 *     public var left: TreeNode?
 *     public var right: TreeNode?
 *     public init() { self.val = 0; self.left = nil; self.right = nil; }
 *     public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
 *     public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
 *         self.val = val
 *         self.left = left
 *         self.right = right
 *     }
 * }
 */
class Solution {
    func generateTrees(_ n: Int) -> [TreeNode?] {
        var dp = [[TreeNode?]?](repeating: nil, count: (n + 1) * (n + 1))

        func generate(_ left: Int, _ right: Int) -> [TreeNode?] {
            if left > right {
                return [nil]
            }
            let key = left * (n + 1) + right
            if let cached = dp[key] {
                return cached
            }

            var res = [TreeNode?]()
            for val in left...right {
                for leftTree in generate(left, val - 1) {
                    for rightTree in generate(val + 1, right) {
                        res.append(TreeNode(val, leftTree, rightTree))
                    }
                }
            }
            dp[key] = res
            return res
        }
        return generate(1, n)
    }
}

impl Solution {
    pub fn generate_trees(n: i32) -> Vec<Option<Rc<RefCell<TreeNode>>>> {
        let n = n as usize;
        let mut dp: Vec<Vec<Option<Vec<Option<Rc<RefCell<TreeNode>>>>>>> =
            vec![vec![None; n + 1]; n + 1];

        fn generate(
            left: usize,
            right: usize,
            dp: &mut Vec<Vec<Option<Vec<Option<Rc<RefCell<TreeNode>>>>>>>,
        ) -> Vec<Option<Rc<RefCell<TreeNode>>>> {
            if left > right {
                return vec![None];
            }
            if let Some(cached) = &dp[left][right] {
                return cached.clone();
            }
            let mut res = vec![];
            for val in left..=right {
                let left_trees = generate(left, val.wrapping_sub(1), dp);
                let right_trees = generate(val + 1, right, dp);
                for lt in &left_trees {
                    for rt in &right_trees {
                        res.push(Some(Rc::new(RefCell::new(TreeNode {
                            val: val as i32,
                            left: lt.clone(),
                            right: rt.clone(),
                        }))));
                    }
                }
            }
            dp[left][right] = Some(res.clone());
            res
        }
        generate(1, n, &mut dp)
    }
}

Time & Space Complexity

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

3. Dynamic Programming (Bottom-Up)

Intuition

We can build the solution iteratively by computing all BSTs for smaller ranges first. We process ranges by increasing length: first all ranges of length 1, then length 2, and so on up to length n. This ensures that when we compute dp[left][right], all smaller subproblems are already solved.

Algorithm

Create a 2D table dp[left][right] to store all BSTs for each range.
Initialize base cases: For each i, set dp[i][i-1] = [null] (empty subtree).
For each length from 1 to n:
- For each starting position left where left + length - 1 <= n:
  - Let right = left + length - 1.
  - For each root value val from left to right:
    - Combine all trees from dp[left][val-1] and dp[val+1][right].
    - Create a new tree node for each combination and add to dp[left][right].
Return dp[1][n].

# 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 + 2)] for _ in range(n + 2)]
        for i in range(1, n + 2):
            dp[i][i - 1] = [None]

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

        return dp[1][n]

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    public List<TreeNode> generateTrees(int n) {
        List<TreeNode>[][] dp = new ArrayList[n + 2][n + 2];
        for (int i = 1; i <= n + 1; i++) {
            dp[i][i - 1] = new ArrayList<>();
            dp[i][i - 1].add(null);
        }

        for (int length = 1; length <= n; length++) {
            for (int left = 1; left + length - 1 <= n; left++) {
                int right = left + length - 1;
                dp[left][right] = new ArrayList<>();

                for (int val = left; val <= right; val++) {
                    for (TreeNode leftTree : dp[left][val - 1]) {
                        for (TreeNode rightTree : dp[val + 1][right]) {
                            dp[left][right].add(new TreeNode(val, leftTree, rightTree));
                        }
                    }
                }
            }
        }
        return dp[1][n];
    }
}

/**
 * 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<vector<TreeNode*>>> dp(n + 2, vector<vector<TreeNode*>>(n + 2));
        for (int i = 1; i <= n + 1; i++) {
            dp[i][i - 1].push_back(nullptr);
        }

        for (int length = 1; length <= n; length++) {
            for (int left = 1; left + length - 1 <= n; left++) {
                int right = left + length - 1;

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

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     constructor(val = 0, left = null, right = null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    /**
     * @param {number} n
     * @return {TreeNode[]}
     */
    generateTrees(n) {
        const dp = Array.from({ length: n + 2 }, () => Array(n + 2).fill(null));
        for (let i = 1; i <= n + 1; i++) {
            dp[i][i - 1] = [null];
        }

        for (let length = 1; length <= n; length++) {
            for (let left = 1; left + length - 1 <= n; left++) {
                let right = left + length - 1;
                dp[left][right] = [];

                for (let val = left; val <= right; val++) {
                    for (let leftTree of dp[left][val - 1]) {
                        for (let rightTree of dp[val + 1][right]) {
                            dp[left][right].push(
                                new TreeNode(val, leftTree, rightTree),
                            );
                        }
                    }
                }
            }
        }
        return dp[1][n];
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    public IList<TreeNode> GenerateTrees(int n) {
        var dp = new List<TreeNode>[n + 2, n + 2];
        for (int i = 1; i <= n + 1; i++) {
            dp[i, i - 1] = new List<TreeNode> { null };
        }

        for (int length = 1; length <= n; length++) {
            for (int left = 1; left + length - 1 <= n; left++) {
                int right = left + length - 1;
                dp[left, right] = new List<TreeNode>();

                for (int val = left; val <= right; val++) {
                    foreach (var leftTree in dp[left, val - 1]) {
                        foreach (var rightTree in dp[val + 1, right]) {
                            dp[left, right].Add(new TreeNode(val, leftTree, rightTree));
                        }
                    }
                }
            }
        }
        return dp[1, n];
    }
}

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func generateTrees(n int) []*TreeNode {
    dp := make([][][]*TreeNode, n+2)
    for i := range dp {
        dp[i] = make([][]*TreeNode, n+2)
    }
    for i := 1; i <= n+1; i++ {
        dp[i][i-1] = []*TreeNode{nil}
    }

    for length := 1; length <= n; length++ {
        for left := 1; left+length-1 <= n; left++ {
            right := left + length - 1
            dp[left][right] = []*TreeNode{}

            for val := left; val <= right; val++ {
                for _, leftTree := range dp[left][val-1] {
                    for _, rightTree := range dp[val+1][right] {
                        dp[left][right] = append(dp[left][right], &TreeNode{val, leftTree, rightTree})
                    }
                }
            }
        }
    }
    return dp[1][n]
}

/**
 * Example:
 * var ti = TreeNode(5)
 * var v = ti.`val`
 * Definition for a binary tree node.
 * class TreeNode(var `val`: Int) {
 *     var left: TreeNode? = null
 *     var right: TreeNode? = null
 * }
 */
class Solution {
    fun generateTrees(n: Int): List<TreeNode?> {
        val dp = Array(n + 2) { Array<MutableList<TreeNode?>?>(n + 2) { null } }
        for (i in 1..n + 1) {
            dp[i][i - 1] = mutableListOf(null)
        }

        for (length in 1..n) {
            for (left in 1..n - length + 1) {
                val right = left + length - 1
                dp[left][right] = mutableListOf()

                for (v in left..right) {
                    for (leftTree in dp[left][v - 1]!!) {
                        for (rightTree in dp[v + 1][right]!!) {
                            dp[left][right]!!.add(TreeNode(v).apply {
                                this.left = leftTree
                                this.right = rightTree
                            })
                        }
                    }
                }
            }
        }
        return dp[1][n]!!
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public var val: Int
 *     public var left: TreeNode?
 *     public var right: TreeNode?
 *     public init() { self.val = 0; self.left = nil; self.right = nil; }
 *     public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
 *     public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
 *         self.val = val
 *         self.left = left
 *         self.right = right
 *     }
 * }
 */
class Solution {
    func generateTrees(_ n: Int) -> [TreeNode?] {
        var dp = [[[TreeNode?]]](repeating: [[TreeNode?]](repeating: [], count: n + 2), count: n + 2)
        for i in 1...n + 1 {
            dp[i][i - 1] = [nil]
        }

        for length in 1...n {
            for left in 1...(n - length + 1) {
                let right = left + length - 1
                dp[left][right] = []

                for val in left...right {
                    for leftTree in dp[left][val - 1] {
                        for rightTree in dp[val + 1][right] {
                            dp[left][right].append(TreeNode(val, leftTree, rightTree))
                        }
                    }
                }
            }
        }
        return dp[1][n]
    }
}

impl Solution {
    pub fn generate_trees(n: i32) -> Vec<Option<Rc<RefCell<TreeNode>>>> {
        let n = n as usize;
        let mut dp: Vec<Vec<Vec<Option<Rc<RefCell<TreeNode>>>>>> =
            vec![vec![vec![]; n + 2]; n + 2];
        for i in 1..=n + 1 {
            dp[i][i - 1] = vec![None];
        }

        for length in 1..=n {
            for left in 1..=(n - length + 1) {
                let right = left + length - 1;
                let mut trees = vec![];
                for val in left..=right {
                    let left_trees = dp[left][val - 1].clone();
                    let right_trees = dp[val + 1][right].clone();
                    for lt in &left_trees {
                        for rt in &right_trees {
                            trees.push(Some(Rc::new(RefCell::new(TreeNode {
                                val: val as i32,
                                left: lt.clone(),
                                right: rt.clone(),
                            }))));
                        }
                    }
                }
                dp[left][right] = trees;
            }
        }
        dp[1][n].clone()
    }
}

Time & Space Complexity

Time complexity: $O(\frac {4 ^ n}{\sqrt {n}})$
Space complexity:
- $O(n ^ 2)$ extra space.
- $O(\frac {4 ^ n}{\sqrt {n}})$ space for the output.

4. Dynamic Programming (Space Optimized)

Intuition

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.

Algorithm

Create an array dp[length] to store all BST structures for trees with length nodes.
Initialize dp[0] = [null] (empty tree).
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].
Define a shift(node, offset) function that creates a new tree with all values increased by offset.
Return dp[n].

# 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

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    public List<TreeNode> generateTrees(int n) {
        List<TreeNode>[] dp = new ArrayList[n + 1];
        dp[0] = new ArrayList<>();
        dp[0].add(null);

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

    private TreeNode shift(TreeNode node, int offset) {
        if (node == null) return null;
        TreeNode root = new TreeNode(node.val + offset);
        root.left = shift(node.left, offset);
        root.right = shift(node.right, offset);
        return root;
    }
}

/**
 * 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;
    }
};

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     constructor(val = 0, left = null, right = null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    /**
     * @param {number} n
     * @return {TreeNode[]}
     */
    generateTrees(n) {
        const shift = (node, offset) => {
            if (!node) return null;
            let root = new TreeNode(node.val + offset);
            root.left = shift(node.left, offset);
            root.right = shift(node.right, offset);
            return root;
        };

        let dp = Array.from({ length: n + 1 }, () => []);
        dp[0].push(null);

        for (let length = 1; length <= n; length++) {
            for (let val = 1; val <= length; val++) {
                for (let leftTree of dp[val - 1]) {
                    for (let rightTree of dp[length - val]) {
                        let root = new TreeNode(val);
                        root.left = leftTree;
                        root.right = shift(rightTree, val);
                        dp[length].push(root);
                    }
                }
            }
        }
        return dp[n];
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    public IList<TreeNode> GenerateTrees(int n) {
        var dp = new List<TreeNode>[n + 1];
        dp[0] = new List<TreeNode> { null };

        for (int length = 1; length <= n; length++) {
            dp[length] = new List<TreeNode>();
            for (int val = 1; val <= length; val++) {
                foreach (var leftTree in dp[val - 1]) {
                    foreach (var rightTree in dp[length - val]) {
                        var root = new TreeNode(val);
                        root.left = leftTree;
                        root.right = Shift(rightTree, val);
                        dp[length].Add(root);
                    }
                }
            }
        }
        return dp[n];
    }

    private TreeNode Shift(TreeNode node, int offset) {
        if (node == null) return null;
        var root = new TreeNode(node.val + offset);
        root.left = Shift(node.left, offset);
        root.right = Shift(node.right, offset);
        return root;
    }
}

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func generateTrees(n int) []*TreeNode {
    var shift func(node *TreeNode, offset int) *TreeNode
    shift = func(node *TreeNode, offset int) *TreeNode {
        if node == nil {
            return nil
        }
        root := &TreeNode{Val: node.Val + offset}
        root.Left = shift(node.Left, offset)
        root.Right = shift(node.Right, offset)
        return root
    }

    dp := make([][]*TreeNode, n+1)
    dp[0] = []*TreeNode{nil}

    for length := 1; length <= n; length++ {
        dp[length] = []*TreeNode{}
        for val := 1; val <= length; val++ {
            for _, leftTree := range dp[val-1] {
                for _, rightTree := range dp[length-val] {
                    root := &TreeNode{Val: val}
                    root.Left = leftTree
                    root.Right = shift(rightTree, val)
                    dp[length] = append(dp[length], root)
                }
            }
        }
    }
    return dp[n]
}

/**
 * Example:
 * var ti = TreeNode(5)
 * var v = ti.`val`
 * Definition for a binary tree node.
 * class TreeNode(var `val`: Int) {
 *     var left: TreeNode? = null
 *     var right: TreeNode? = null
 * }
 */
class Solution {
    fun generateTrees(n: Int): List<TreeNode?> {
        fun shift(node: TreeNode?, offset: Int): TreeNode? {
            if (node == null) return null
            val root = TreeNode(node.`val` + offset)
            root.left = shift(node.left, offset)
            root.right = shift(node.right, offset)
            return root
        }

        val dp = Array<MutableList<TreeNode?>>(n + 1) { mutableListOf() }
        dp[0].add(null)

        for (length in 1..n) {
            for (v in 1..length) {
                for (leftTree in dp[v - 1]) {
                    for (rightTree in dp[length - v]) {
                        val root = TreeNode(v)
                        root.left = leftTree
                        root.right = shift(rightTree, v)
                        dp[length].add(root)
                    }
                }
            }
        }
        return dp[n]
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public var val: Int
 *     public var left: TreeNode?
 *     public var right: TreeNode?
 *     public init() { self.val = 0; self.left = nil; self.right = nil; }
 *     public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
 *     public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
 *         self.val = val
 *         self.left = left
 *         self.right = right
 *     }
 * }
 */
class Solution {
    func generateTrees(_ n: Int) -> [TreeNode?] {
        func shift(_ node: TreeNode?, _ offset: Int) -> TreeNode? {
            guard let node = node else { return nil }
            let root = TreeNode(node.val + offset)
            root.left = shift(node.left, offset)
            root.right = shift(node.right, offset)
            return root
        }

        var dp = [[TreeNode?]](repeating: [], count: n + 1)
        dp[0] = [nil]

        for length in 1...n {
            for val in 1...length {
                for leftTree in dp[val - 1] {
                    for rightTree in dp[length - val] {
                        let root = TreeNode(val)
                        root.left = leftTree
                        root.right = shift(rightTree, val)
                        dp[length].append(root)
                    }
                }
            }
        }
        return dp[n]
    }
}

impl Solution {
    pub fn generate_trees(n: i32) -> Vec<Option<Rc<RefCell<TreeNode>>>> {
        fn shift(node: &Option<Rc<RefCell<TreeNode>>>, offset: i32) -> Option<Rc<RefCell<TreeNode>>> {
            match node {
                None => None,
                Some(n) => {
                    let n = n.borrow();
                    Some(Rc::new(RefCell::new(TreeNode {
                        val: n.val + offset,
                        left: shift(&n.left, offset),
                        right: shift(&n.right, offset),
                    })))
                }
            }
        }

        let n = n as usize;
        let mut dp: Vec<Vec<Option<Rc<RefCell<TreeNode>>>>> = vec![vec![]; n + 1];
        dp[0] = vec![None];

        for length in 1..=n {
            let mut trees = vec![];
            for val in 1..=length {
                let left_trees = dp[val - 1].clone();
                let right_trees = dp[length - val].clone();
                for lt in &left_trees {
                    for rt in &right_trees {
                        let root = Rc::new(RefCell::new(TreeNode {
                            val: val as i32,
                            left: lt.clone(),
                            right: shift(rt, val as i32),
                        }));
                        trees.push(Some(root));
                    }
                }
            }
            dp[length] = trees;
        }
        dp[n].clone()
    }
}

Time & Space 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.

Common Pitfalls

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.