Skip to main content
Talentd

Unique Binary Search Trees II - Solution & Explanation

MediumDynamic ProgrammingBacktrackingTreeBinary Search Tree20 min readAsked at: Amazon, Microsoft, Meta +2
Practice this problem

Problem Statement

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.

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.

Code

PythonCC++JavaC#JavaScript

Python

C

C++

Java

C#

JavaScript

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.

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.

Code

PythonC++Java

Python

C++

Java

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:

  1. 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.
  2. 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.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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)—

Detailed Complexity Analysis

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

Video Solution

Unique Binary Search Trees II - Leetcode 95 - Python • NeetCodeIO • 33,650 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Unique Binary Search Trees II with our built-in code editor and test cases.

Practice on FleetCode
Previous

Different Ways to Add Parentheses

Next

Unique Binary Search Trees