96. Unique Binary Search Trees
Unique Binary Search Trees (LeetCode 96) 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.
How to solve Unique Binary Search Trees
Unique Binary Search Trees is a Catalan Numbers DP problem, part of Dynamic Programming (DP) Patterns. Solve problems involving Catalan numbers: unique BSTs, parentheses combinations, polygon triangulation.
Work towards the solution in these steps:
- Consider how dynamic programming can help break down the problem of counting unique BSTs into smaller, manageable subproblems.
- Think about how choosing a root node divides the BST into left and right subtrees, each of which can be counted independently.
- Try to express the total number of unique BSTs for n nodes as a sum over all possible root nodes, multiplying the counts of left and right subtree possibilities.
The reference solution runs in O(n^2) time and O(n) space.
The Unique Binary Search Trees solution and editorial walks through the full approach with reference code.
Problem statement
Given an integer n, return the number of structurally unique BST's (binary search trees) which has exactly n nodes of unique values from 1 to n.
Example 1:
Input: n = 3 Output: 5
Example 2:
Input: n = 1 Output: 1
Constraints:
- 1 <= n <= 19
Topics and companies
Topics: Math, Dynamic Programming, Tree, Binary Search Tree, Binary Tree.
Reported in interviews at Microsoft, Bloomberg.
How to practise Unique Binary Search Trees 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(n^2) time and O(n) space.
Open Unique Binary Search Trees in the code editor, or read the Unique Binary Search Trees editorial for a worked solution with its approach and complexity analysis.
Where Unique Binary Search Trees sits in the DSA pattern sheet
- Dynamic Programming (DP) Patterns pattern guide
- Catalan Numbers subpattern
- The full DSA patterns sheet
Problems related to Unique Binary Search Trees
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 II — 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
Unique Binary Search Trees FAQ
What is the LeetCode number of Unique Binary Search Trees?
Unique Binary Search Trees is LeetCode problem 96, rated Medium.
What pattern is used to solve Unique Binary Search Trees?
Unique Binary Search Trees is a Catalan Numbers DP problem. It belongs to the Dynamic Programming (DP) Patterns pattern, in the Catalan Numbers subpattern.
What is the time complexity of Unique Binary Search Trees?
The reference solution runs in O(n^2) time and O(n) space.
Which companies ask Unique Binary Search Trees?
Unique Binary Search Trees has been reported in interviews at Microsoft, Bloomberg.