96. Unique Binary Search Trees
Problem Description
The problem asks for the number of structurally unique Binary Search Trees (BSTs) that can be formed using exactly n
nodes, each node having a unique value from 1 to n
. A Binary Search Tree is a tree where each node satisfies the following conditions:
- The left subtree of a node contains only nodes with keys less than the node's key.
- The right subtree of a node contains only nodes with keys greater than the node's key.
- Both the left and right subtrees must also be binary search trees.
Understanding this, we need to calculate the count of all possible unique tree structures without considering the actual node values, as the unique values will be distributed in the same structure in exactly one way due to BST property.
Intuition
To solve this problem, we can use a method known as dynamic programming. Dynamic programming breaks down the problem into smaller subproblems and uses the results of these subproblems to solve larger ones.
The intuition behind the solution can be understood in terms of the following points:
- Consider that the number of unique BSTs with
0
nodes (an empty tree) is1
. This serves as our base case. - The key to solving the problem is realizing that when we choose a number
i
from1
ton
to be the root of a BST, then1
toi-1
will necessarily form the left subtree andi+1
ton
will form the right subtree. - The number of unique BSTs that can be formed with
i
as the root is the product of the number of unique BSTs that can be formed with1
toi-1
and the number of unique BSTs that can be formed withi+1
ton
. - Thus, we iterate through all numbers from
1
ton
, treating each as the root, and multiply the number of ways to form left and right subtrees, summing these products up to get the total number of unique BSTs forn
nodes.
The dynamic programming array dp
will hold the solution to our subproblems where dp[i]
represents the number of unique BSTs that can be formed with i
distinct nodes. We iteratively fill up this array by using the results of smaller subproblems to build the solutions to larger subproblems.
Learn more about Tree, Binary Search Tree, Math, Dynamic Programming and Binary Tree patterns.
Solution Approach
The solution uses dynamic programming to build up the number of unique BSTs that can be formed for each number of nodes from 0
to n
. The following steps are executed in the solution:
-
A list
dp
is initialized withn + 1
elements, all set to0
. This list holds the solutions to our subproblems wheredp[i]
gives the number of unique BSTs that can be formed withi
nodes. Since we start counting nodes from1
, we make our list one element larger thann
to make it easier to refer todp[n]
. -
The first element
dp[0]
is set to1
. This represents the fact that there is exactly one BST that can be formed with0
nodes, the empty tree. -
We then use a nested loop where we consider every number
i
from1
ton
to represent the number of nodes we are currently interested in. For eachi
, we consider every possible rootj
from1
toi
. Hence, we calculate the number of unique trees withj
as the root by multiplying the number of unique trees that can be formed withj-1
nodes (left subtree) andi-j
nodes (right subtree). -
For each
i
andj
, we update thedp
array by adding the productdp[j] * dp[i - j - 1]
todp[i]
. This is done because whenj
is the root, there aredp[j]
ways to construct the left subtree from0
toj-1
anddp[i - j - 1]
ways to construct the right subtree fromj+1
toi
. Since the root is fixed, the left and right subtrees form independently of each other; thus the total number is the product of possibilities for each side. -
After the loops complete,
dp[n]
contains the final result, which is the number of unique BSTs that can be made withn
distinct nodes.
In our case, dp[-1]
is equivalent to dp[n]
since Python supports negative indexing and refers to the last element of the list. This value is then returned by the function.
This implementation uses a bottom-up approach, and each subproblem is solved only once and then reused, leading to an efficient algorithm with a time complexity of O(n^2). The space complexity is O(n), as we need to store the number of unique BSTs for each number from 0
to n
.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
To illustrate the solution approach, let's walk through a small example where n = 3
. We are seeking to find the number of structurally unique BSTs that can be formed with nodes valued from 1
to 3
.
According to the solution approach, these are the steps we would follow:
-
Initialize a dynamic programming list
dp
of sizen+1
and set all its elements to0
. This list will store the number of unique BSTs for each number of nodes, so in our case,dp = [0, 0, 0, 0]
. -
Set the base case
dp[0]
to1
, which represents the count of unique BSTs with0
nodes (empty tree). It means that ourdp
list now looks like this:dp = [1, 0, 0, 0]
. -
Now, we need to compute
dp[i]
for eachi
from1
ton
. Let's start by findingdp[1]
.- For
i = 1
(with only one node), regardless of the value, there's only one way to create a BST. So,dp[1] = 1
.
- For
-
Let's move on to compute
dp[2]
(two nodes). We have two scenarios here:- We pick
1
as the root. There isdp[0]
ways to arrange the left subtree since there are zero nodes to the left of1
, anddp[1]
ways to arrange the right subtree, with just one node2
. - We pick
2
as the root. There isdp[1]
ways to arrange the left subtree with just one node1
, anddp[0]
ways for the right subtree since there are no nodes to the right of2
. - The total, combining both scenarios, gives us
dp[2] = dp[0]*dp[1] + dp[1]*dp[0] = 1*1 + 1*1 = 2
.
- We pick
-
Finally, we have to compute
dp[3]
.- Picking
1
as the root: No nodes on the left, so we havedp[0]
ways; and two nodes on the right (2
and3
), giving usdp[2]
ways. - Picking
2
as the root: One node on the left (1
), sodp[1]
ways; and one node on the right (3
), alsodp[1]
ways. - Picking
3
as the root: Two nodes on the left (1
and2
), sodp[2]
ways; and no nodes on the right, givingdp[0]
ways. - We sum up all these products to get:
dp[3] = dp[0]*dp[2] + dp[1]*dp[1] + dp[2]*dp[0] = 1*2 + 1*1 + 2*1 = 5
.
- Picking
So, the array dp
at the end of our computation is [1, 1, 2, 5]
. The number of unique BSTs that can be formed with 3
nodes is dp[3]
, which is 5
. Hence, the function would return 5
for n = 3
. This method can be extended for any larger n
, using the same dynamic programming approach.
Solution Implementation
1class Solution:
2 def numTrees(self, n: int) -> int:
3 # Initialize a list for dynamic programming with a size of n + 1.
4 # Set the first element to 1 because there's exactly one structure for an empty tree.
5 num_trees = [0] * (n + 1)
6 num_trees[0] = 1
7
8 # Build the number of unique BSTs (Binary Search Trees) for each count of nodes
9 # from 1 up to and including n. The outer loop goes through numbers of nodes.
10 for nodes in range(1, n + 1):
11 # The inner loop goes through the number of nodes by considering all possible left subtrees
12 # (which are represented by j) and right subtrees (which are represented by nodes - j - 1).
13 for left_tree_nodes in range(nodes):
14 # The number of unique BSTs with 'nodes' nodes is the sum of
15 # the number of unique BSTs for each left subtree (j) multiplied by
16 # the number of unique BSTs for each right subtree (nodes - j - 1).
17 num_trees[nodes] += num_trees[left_tree_nodes] * num_trees[nodes - left_tree_nodes - 1]
18
19 # The last element of the list will hold the result for n nodes.
20 return num_trees[-1]
21
1class Solution {
2 // Function to compute number of unique BSTs with n nodes
3 public int numTrees(int n) {
4 // Initialise the dp array to store the number of unique BSTs for each count of nodes
5 int[] dp = new int[n + 1];
6
7 // There is one unique BST for a tree with zero nodes, which is an empty tree
8 dp[0] = 1;
9
10 // Iterate over each count of nodes from 1 to n
11 for (int nodes = 1; nodes <= n; ++nodes) {
12 // Calculate the number of unique BSTs for 'nodes' number of nodes
13 for (int root = 0; root < nodes; ++root) {
14 // For each position 'root', the number of trees is the product of the
15 // number of unique trees in the left subtree (dp[root])
16 // and the number of unique trees in the right subtree (dp[nodes - root - 1]).
17 dp[nodes] += dp[root] * dp[nodes - root - 1];
18 }
19 }
20
21 // Return the result for n nodes
22 return dp[n];
23 }
24}
25
1class Solution {
2public:
3 // Function to compute the number of unique BSTs (Binary Search Trees) that can be constructed with 'n' distinct nodes
4 int numTrees(int n) {
5 // Create a dp (Dynamic Programming) vector with 'n+1' elements initialized to 0
6 // dp[i] will store the number of unique BSTs that can be constructed with 'i' nodes
7 vector<int> dp(n + 1, 0);
8
9 // The number of BSTs with 0 nodes (empty tree) is 1
10 dp[0] = 1;
11
12 // Build up the number of BSTs for each number of nodes from 1 to 'n'
13 for (int nodes = 1; nodes <= n; ++nodes) {
14 // Iterate through all possible left subtrees with 'left' nodes
15 for (int left = 0; left < nodes; ++left) {
16 // The number of right nodes is 'nodes - left - 1' (because one node is the root)
17 int right = nodes - left - 1;
18 // Multiply the number of ways to construct the left subtree with 'left' nodes
19 // by the number of ways to construct the right subtree with 'right' nodes
20 dp[nodes] += dp[left] * dp[right];
21 }
22 }
23
24 // The result is the number of unique BSTs that can be constructed with 'n' nodes
25 return dp[n];
26 }
27};
28
1// Function to compute the number of unique BSTs (Binary Search Trees)
2// that can be constructed with 'n' distinct nodes
3function numTrees(n: number): number {
4 // Create a dp (Dynamic Programming) array with 'n+1' elements initialized to 0
5 // dp[i] will store the number of unique BSTs that can be constructed with 'i' nodes
6 let dp: number[] = new Array(n + 1).fill(0);
7
8 // The number of BSTs with 0 nodes (empty tree) is 1
9 dp[0] = 1;
10
11 // Build up the number of BSTs for each number of nodes from 1 to 'n'
12 for (let nodes = 1; nodes <= n; nodes++) {
13 // Iterate through all possible left subtrees with 'left' nodes
14 for (let left = 0; left < nodes; left++) {
15 // The number of right nodes is 'nodes - left - 1' (because one node is the root)
16 let right = nodes - left - 1;
17 // Multiply the number of ways to construct the left subtree with 'left' nodes
18 // by the number of ways to construct the right subtree with 'right' nodes
19 dp[nodes] += dp[left] * dp[right];
20 }
21 }
22
23 // The result is the number of unique BSTs that can be constructed with 'n' nodes
24 return dp[n];
25}
26
Time and Space Complexity
The given code is designed to calculate the number of structurally unique BSTs (binary search trees) that store values 1 through n
using dynamic programming. To analyze the time and space complexity, we will consider the main operations and how they scale with respect to the input n
.
Time Complexity
- We initialize a list
dp
of sizen+1
with zero, which takesO(n)
time. - There is a nested loop where the outer loop runs from
1
ton
and the inner loop runsi
times (which is at mostn
times wheni=n
). - Within the inner loop, the corresponding element in
dp
is updated, and this operation is constant time,O(1)
. - Thus, the time complexity for the nested loops can be approximated as the sum of the first
n
natural numbers, which isO(n^2)
.
Therefore, the overall time complexity of the code is O(n^2)
.
Space Complexity
- We have a list
dp
that containsn+1
elements, which represents the space complexity ofO(n)
. - No other data structures are used that grow with
n
, soO(n)
represents the total space complexity.
In conclusion, the time complexity of the code is O(n^2)
and the space complexity is O(n)
.
Learn more about how to find time and space complexity quickly using problem constraints.
Consider the classic dynamic programming of fibonacci numbers, what is the recurrence relation?
Recommended Readings
Everything About Trees A tree is a type of graph data structure composed of nodes and edges Its main properties are It is acyclic doesn't contain any cycles There exists a path from the root to any node Has N 1 edges where N is the number of nodes in the tree and
Binary Search Tree Intro Definition A Binary Search Tree or BST is a rooted binary tree with the value of each internal node being greater than all the values in the respective node's left subtree and less than the ones in its right subtree An empty tree is a BST since it satisfies the
Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.