Unique Binary Search Trees II

Unique Binary Search Trees II is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Dynamic Programming (DP) Patterns pattern, in the Catalan Numbers subpattern.

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

Topics and companies

Topics: Dynamic Programming, Backtracking, Tree, Binary Search Tree, Binary Tree.

Reported in interviews at Amazon, Google.

How to practise Unique Binary Search Trees II on Thita.ai

Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(C_n * n^2), where C_n is the nth Catalan number. For each unique BST (C_n), we perform a level-order traversal (O(n)) and tree construction (O(n)), so total is O(C_n * n^2). time and O(C_n * n), where C_n is the nth Catalan number. We store all unique BSTs (each with up to n nodes), and the output vector of their level-order traversals. space.

Open Unique Binary Search Trees II in the code editor, or read the Unique Binary Search Trees II editorial for a worked solution with its approach and complexity analysis.

Where Unique Binary Search Trees II sits in the DSA pattern sheet

• Dynamic Programming (DP) Patterns pattern guide
• Catalan Numbers subpattern
• The full DSA patterns sheet
• All coding practice problems

Problems related to Unique Binary Search Trees II

Other problems that use the same Catalan Numbers and Dynamic Programming (DP) Patterns techniques:

• Different Ways to Add Parentheses — Medium, same subpattern
• Unique Binary Search Trees — Medium, same subpattern
• Best Time to Buy and Sell Stock — Easy, same pattern
• Best Time to Buy and Sell Stock II — Medium, same pattern
• Best Time to Buy and Sell Stock III — Hard, same pattern
• Best Time to Buy and Sell Stock IV — Hard, same pattern