95. Unique Binary Search Trees II - Solution

The problem

Given an integer n, return all the structurally unique BST's (binary search trees), which has exactly n nodes of unique values from 1 to n. Return the answer in any order.

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 2:

Input: n = 1
Output: [[1]]

Constraints:

1 <= n <= 8

Approach overview

Problem Overview: Given an integer n, generate every structurally unique Binary Search Tree that stores values from 1 to n. Each tree must follow BST ordering rules, and the result returns the root node of every valid tree configuration.

Approach 1: Recursive Tree Construction (Backtracking) (Time: O(Cn * n), Space: O(Cn * n))

This approach builds trees by choosing every number in the range [start, end] as the root. For a chosen root i, recursively generate all left subtrees from [start, i-1] and all right subtrees from [i+1, end]. Then combine every left subtree with every right subtree to form complete trees. The recursion explores all possible root choices, which naturally generates every valid structure. The total number of generated trees follows the Catalan sequence (Cn), which leads to exponential growth in the number of outputs.

This technique is essentially backtracking over root selections while constructing nodes that satisfy binary search tree ordering rules. It’s simple and mirrors the recursive definition of BSTs, making it the most common interview implementation.

Approach 2: Dynamic Programming with Memoization (Time: O(Cn * n), Space: O(Cn * n))

The recursive solution repeatedly recomputes subtrees for the same ranges. Memoization removes that duplication. Cache the result of generate(start, end) in a hash map or 2D table so the subtree list is built only once. When the recursion encounters the same range again, return the cached trees instead of rebuilding them.

This converts the brute recursive exploration into a classic dynamic programming problem over intervals. Each state represents all BSTs formed from a specific number range. Although the total number of produced trees is still Catalan-sized, memoization significantly reduces repeated recursion and improves practical performance.

Recommended for interviews: Start with the recursive tree construction because it clearly demonstrates understanding of BST structure and recursive decomposition. Then mention memoization as an optimization to eliminate repeated subtree generation. Interviewers typically expect the recursive formulation first, followed by the DP improvement.

Approach 1: Recursive Tree Construction

This approach involves dividing the set of integers from 1 to n into left and right subtrees recursively for each possible root value. For each possible root node, the values less than the root form the left subtree and the values greater than the root form the right subtree. We repeat this process recursively to construct all unique BSTs by selecting each number in the range as the root.

Python

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

def generate_trees(start, end):
    if start > end:
        return [None]
    all_trees = []
    for i in range(start, end + 1):
        left_trees = generate_trees(start, i - 1)
        right_trees = generate_trees(i + 1, end)
        for l in left_trees:
            for r in right_trees:
                current_tree = TreeNode(i)
                current_tree.left = l
                current_tree.right = r
                all_trees.append(current_tree)
    return all_trees

def generate_trees_main(n):
    if n == 0:
        return []
    return generate_trees(1, n)

Java

import java.util.*;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

public class UniqueBST {
    public List<TreeNode> generateTrees(int n) {
        if (n == 0) return new ArrayList<>();
        return generateTrees(1, n);
    }

    private List<TreeNode> generateTrees(int start, int end) {
        List<TreeNode> allTrees = new ArrayList<>();
        if (start > end) {
            allTrees.add(null);
            return allTrees;
        }

        for (int i = start; i <= end; i++) {
            List<TreeNode> leftTrees = generateTrees(start, i - 1);
            List<TreeNode> rightTrees = generateTrees(i + 1, end);
            for (TreeNode left : leftTrees) {
                for (TreeNode right : rightTrees) {
                    TreeNode root = new TreeNode(i);
                    root.left = left;
                    root.right = right;
                    allTrees.add(root);
                }
            }
        }
        return allTrees;
    }
}

C++

#include <vector>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

vector<TreeNode*> generateTrees(int start, int end) {
    if (start > end) return {NULL};
    vector<TreeNode*> allTrees;
    for (int i = start; i <= end; ++i) {
        vector<TreeNode*> leftTrees = generateTrees(start, i - 1);
        vector<TreeNode*> rightTrees = generateTrees(i + 1, end);
        for (auto left : leftTrees) {
            for (auto right : rightTrees) {
                TreeNode* root = new TreeNode(i);
                root->left = left;
                root->right = right;
                allTrees.push_back(root);
            }
        }
    }
    return allTrees;
}

vector<TreeNode*> generateTrees(int n) {
    if (n == 0) return {};
    return generateTrees(1, n);
}

JavaScript

function TreeNode(val) {
    this.val = val;
    this.left = this.right = null;
}

var generateTrees = function(n) {
    if (n == 0) return [];
    return generateTreesRange(1, n);
};

function generateTreesRange(start, end) {
    let allTrees = [];
    if (start > end) {
        allTrees.push(null);
        return allTrees;
    }

    for (let i = start; i <= end; i++) {
        let leftTrees = generateTreesRange(start, i - 1);
        let rightTrees = generateTreesRange(i + 1, end);

        for (const left of leftTrees) {
            for (const right of rightTrees) {
                const currentTree = new TreeNode(i);
                currentTree.left = left;
                currentTree.right = right;
                allTrees.push(currentTree);
            }
        }
    }
    return allTrees;
}

#include <stdio.h>
#include <stdlib.h>

struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

struct TreeNode* createNode(int val) {
    struct TreeNode* newNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    newNode->val = val;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

struct TreeNode** generateTrees(int start, int end, int* returnSize) {
    struct TreeNode** allTrees = (struct TreeNode**)malloc(1000 * sizeof(struct TreeNode*));
    if (start > end) {
        *returnSize = 1;
        allTrees[0] = NULL;
        return allTrees;
    }
    int size = 0;
    for (int i = start; i <= end; ++i) {
        int leftSize = 0, rightSize = 0;
        struct TreeNode** leftTrees = generateTrees(start, i - 1, &leftSize);
        struct TreeNode** rightTrees = generateTrees(i + 1, end, &rightSize);
        for (int l = 0; l < leftSize; ++l) {
            for (int r = 0; r < rightSize; ++r) {
                struct TreeNode* root = createNode(i);
                root->left = leftTrees[l];
                root->right = rightTrees[r];
                allTrees[size++] = root;
            }
        }
    }
    *returnSize = size;
    return allTrees;
}

struct TreeNode** generateTreesMain(int n, int* returnSize) {
    if (n == 0) {
        *returnSize = 0;
        return NULL;
    }
    return generateTrees(1, n, returnSize);
}

using System;
using System.Collections.Generic;

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int x) { val = x; }
}

public class Solution {
    public IList<TreeNode> GenerateTrees(int n) {
        if (n == 0) return new List<TreeNode>();
        return GenerateTrees(1, n);
    }

    private IList<TreeNode> GenerateTrees(int start, int end) {
        IList<TreeNode> allTrees = new List<TreeNode>();
        if (start > end) {
            allTrees.Add(null);
            return allTrees;
        }

        for (int i = start; i <= end; i++) {
            var leftTrees = GenerateTrees(start, i - 1);
            var rightTrees = GenerateTrees(i + 1, end);
            foreach (var left in leftTrees) {
                foreach (var right in rightTrees) {
                    TreeNode root = new TreeNode(i);
                    root.left = left;
                    root.right = right;
                    allTrees.Add(root);
                }
            }
        }
        return allTrees;
    }
}

This Python code defines a TreeNode class and a recursive function 'generate_trees' that builds all unique BSTs for integers between 'start' and 'end'. It selects each number as the root and recursively builds left and right subtrees.

Complexity

Time Complexity: O(4^n / √n) where n is the number of nodes because it involves generating all unique trees which is a Catalan number problem.
Space Complexity: O(4^n / √n) for storing the results.

Try this approach in the editor

Approach 2: Dynamic Programming with Memoization

This approach involves leveraging dynamic programming to store results of previously evaluated subproblems to optimize the recursive solution. We maintain a memoization table to store precalculated trees for specific ranges, aiding efficient calculation by reducing the re-computation of the same subproblems.

Python

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

from functools import lru_cache

def generate_trees(start, end):
    if start > end:
        return [None]
    all_trees = []
    for i in range(start, end + 1):
        left_trees = generate_trees(start, i - 1)
        right_trees = generate_trees(i + 1, end)
        for l in left_trees:
            for r in right_trees:
                current_tree = TreeNode(i)
                current_tree.left = l
                current_tree.right = r
                all_trees.append(current_tree)
    return all_trees

generate_trees = lru_cache(None)(generate_trees)

def generate_trees_main(n):
    if n == 0:
        return []
    return generate_trees(1, n)

Java

import java.util.*;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

public class UniqueBST {
    private Map<String, List<TreeNode>> memo = new HashMap<>();

    public List<TreeNode> generateTrees(int n) {
        if (n == 0) return new ArrayList<>();
        return generateTrees(1, n);
    }

    private List<TreeNode> generateTrees(int start, int end) {
        List<TreeNode> allTrees = new ArrayList<>();
        if (start > end) {
            allTrees.add(null);
            return allTrees;
        }
        String key = start + "," + end;
        if (memo.containsKey(key)) return memo.get(key);

        for (int i = start; i <= end; i++) {
            List<TreeNode> leftTrees = generateTrees(start, i - 1);
            List<TreeNode> rightTrees = generateTrees(i + 1, end);
            for (TreeNode left : leftTrees) {
                for (TreeNode right : rightTrees) {
                    TreeNode root = new TreeNode(i);
                    root.left = left;
                    root.right = right;
                    allTrees.add(root);
                }
            }
        }
        memo.put(key, allTrees);
        return allTrees;
    }
}

C++

#include <vector>
#include <unordered_map>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

unordered_map<int, vector<TreeNode*>> memo;

vector<TreeNode*> generateTrees(int start, int end) {
    if (start > end) return {NULL};
    int key = start * 100 + end;
    if (memo.count(key)) return memo[key];
    vector<TreeNode*> allTrees;
    for (int i = start; i <= end; ++i) {
        vector<TreeNode*> leftTrees = generateTrees(start, i - 1);
        vector<TreeNode*> rightTrees = generateTrees(i + 1, end);
        for (auto left : leftTrees) {
            for (auto right : rightTrees) {
                TreeNode* root = new TreeNode(i);
                root->left = left;
                root->right = right;
                allTrees.push_back(root);
            }
        }
    }
    return memo[key] = allTrees;
}

vector<TreeNode*> generateTrees(int n) {
    if (n == 0) return {};
    return generateTrees(1, n);
}

This Python code employs memoization via the 'lru_cache' decorator to efficiently store and reuse the results of previously computed subproblems within the recursive 'generate_trees' function.

Complexity

Time Complexity: O(4^n / √n) due to solving subproblems exactly once.
Space Complexity: O(4^n / √n) for storing the memoized results.

Try this approach in the editor

Approach 3: 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).

The execution steps of the function dfs(i, j) are as follows:

If i > j, it means that there are no numbers to form a binary search tree at this time, so return a list consisting of a null node.
If i leq j, we enumerate the numbers v in [i, j] as the root node. The left subtree of the root node v is composed of [i, v - 1], and the right subtree is composed of [v + 1, j]. Finally, we take the Cartesian product of all combinations of the left and right subtrees, i.e., left times right, add the root node v, and get all binary search trees with v as the root node.

The time complexity is O(n times G(n)), and the space complexity is O(n times G(n)). Where G(n) is the Catalan number.

TypeScript

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function generateTrees(n: number): Array<TreeNode | null> {
    const dfs = (i: number, j: number): Array<TreeNode | null> => {
        if (i > j) {
            return [null];
        }
        const ans: Array<TreeNode | null> = [];
        for (let v = i; v <= j; ++v) {
            const left = dfs(i, v - 1);
            const right = dfs(v + 1, j);
            for (const l of left) {
                for (const r of right) {
                    ans.push(new TreeNode(v, l, r));
                }
            }
        }
        return ans;
    };
    return dfs(1, n);
}

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func generateTrees(n int) []*TreeNode {
	var dfs func(int, int) []*TreeNode
	dfs = func(i, j int) []*TreeNode {
		if i > j {
			return []*TreeNode{nil}
		}
		ans := []*TreeNode{}
		for v := i; v <= j; v++ {
			left := dfs(i, v-1)
			right := dfs(v+1, j)
			for _, l := range left {
				for _, r := range right {
					ans = append(ans, &TreeNode{v, l, r})
				}
			}
		}
		return ans
	}
	return dfs(1, n)
}

Rust

// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
//   pub val: i32,
//   pub left: Option<Rc<RefCell<TreeNode>>>,
//   pub right: Option<Rc<RefCell<TreeNode>>>,
// }
//
// impl TreeNode {
//   #[inline]
//   pub fn new(val: i32) -> Self {
//     TreeNode {
//       val,
//       left: None,
//       right: None
//     }
//   }
// }
use std::cell::RefCell;
use std::rc::Rc;
impl Solution {
    pub fn generate_trees(n: i32) -> Vec<Option<Rc<RefCell<TreeNode>>>> {
        Self::dfs(1, n)
    }

    fn dfs(i: i32, j: i32) -> Vec<Option<Rc<RefCell<TreeNode>>>> {
        let mut ans = Vec::new();
        if i > j {
            ans.push(None);
            return ans;
        }
        for v in i..=j {
            let left = Self::dfs(i, v - 1);
            let right = Self::dfs(v + 1, j);
            for l in &left {
                for r in &right {
                    ans.push(Some(Rc::new(RefCell::new(TreeNode {
                        val: v,
                        left: l.clone(),
                        right: r.clone(),
                    }))));
                }
            }
        }
        ans
    }
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Recursive Tree Construction	Time Complexity: O(4^n / √n) where n is the number of nodes because it involves generating all unique trees which is a Catalan number problem. Space Complexity: O(4^n / √n) for storing the results.
Dynamic Programming with Memoization	Time Complexity: O(4^n / √n) due to solving subproblems exactly once. Space Complexity: O(4^n / √n) for storing the memoized results.
DFS (Depth-First Search)	–

Complexity analysis

Approach	Time	Space	When to Use
Recursive Tree Construction (Backtracking)	O(Cn * n)	O(Cn * n)	Best for interviews and understanding BST structure. Straightforward recursion.
Dynamic Programming with Memoization	O(Cn * n)	O(Cn * n)	Use when avoiding repeated subtree computation. More efficient for larger n.

Frequently asked questions

Is Unique Binary Search Trees II easy or hard?

Unique Binary Search Trees II is considered a Medium problem on LeetCode. The recursion concept is straightforward, but recognizing that each number can act as a root and combining all subtree permutations requires a solid understanding of recursion, BST properties, and Catalan-number growth.

Unique Binary Search Trees II Python/Java solution

In Python or Java, implement a recursive function that returns all BST roots for a range [start, end]. For each root choice i, generate all left subtrees from [start, i-1] and right subtrees from [i+1, end], then combine them. Memoization using a dictionary or map improves performance.

How to solve Unique Binary Search Trees II in O(n)?

Generating all unique BST structures cannot be done in O(n) because the output size itself is exponential (Catalan growth). The optimal approach enumerates all trees using recursion or dynamic programming, which requires O(Cn * n) time since every valid structure must be built.

What is the best approach for Unique Binary Search Trees II?

Recursive tree construction with memoization is the most practical approach. Choose each value as the root, recursively generate all left and right subtrees, and combine them. Adding memoization avoids recomputing subtree ranges and keeps the solution efficient while still generating all Catalan-number trees.

Is Unique Binary Search Trees II asked at Google/Amazon/Meta?

Tree construction and Catalan-number problems appear frequently in interviews at companies like Google, Amazon, and Meta. Variants involving BST generation, subtree combinations, or counting unique trees are common interview patterns in tree and dynamic programming categories.

What data structure is used in Unique Binary Search Trees II?

The solution primarily uses binary trees, specifically Binary Search Trees. Recursion builds tree nodes, and dynamic programming with memoization may use a hash map or 2D cache to store lists of previously computed subtree structures.

What is the time complexity of Unique Binary Search Trees II?

The time complexity is O(Cn * n), where Cn is the nth Catalan number. The algorithm must generate every valid BST structure, and the number of such trees grows roughly as 4^n / (n^(3/2)). Each generated tree also requires node connections, contributing the extra factor of n.

Unique Binary Search Trees II solution and explanation

The problem

Approach overview

Approach 1: Recursive Tree Construction

Approach 2: Dynamic Programming with Memoization

Approach 3: DFS (Depth-First Search)

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Unique Binary Search Trees II solution and explanation

The problem

Approach overview

Approach 1: Recursive Tree Construction

Approach 2: Dynamic Programming with Memoization

Approach 3: DFS (Depth-First Search)

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems