Problem Description
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
The description was taken from https://leetcode.com/problems/unique-binary-search-trees/.
Problem Solution
#O(N^2) Time, O(N) Space
class Solution:
def numTrees(self, n: int) -> int:
dp = [0] * (n+1)
dp[0], dp[1] = 1, 1 for i in range(2, n+1):
for j in range(1, i+1):
dp[i] += dp[j-1] * dp[i-j] return dp[-1]
Problem Explanation
If we are given a number input and are asked the total amount of combinations of x there could be from that number, typically Dynamic Programming can be applied.
Similar to other Dynamic Programming problems, we will try to break the problem into subproblems.
This question is asking the number of structurally unique BSTs which has exactly n nodes of unique values from 1 to n.
The subproblems we can break this down to is:
The number of structurally unique BSTs that have exactly 0 nodes of unique values.
The number of structurally unique BSTs that have exactly 1 nodes of unique values.
The number of structurally unique BSTs that have exactly 2 nodes of unique values.
.
.
.
The number of structurally unique BSTs that have exactly n nodes of unique values.
To solve each subproblem, we will simulate creating these trees. To simulate creating these trees, we will traverse through the number of nodes within the given subproblem and set each node as a root. By doing this, we will be able to rely on previous subproblems to answer the current one.
If we exclude the root from the number of combinations, then we can rely on the root's left and right children to give us the answer to how many combinations there would be for the given subproblem if the current node was the root. The reason for this is each child will be its own subtree, and each subtree will have its number of combinations calculated within a previous subproblem that we can utilize and won't have to keep recalculating these values.
Essentially we will have a subproblem where we will find the number of combinations we have for the current number of nodes, and each subproblem will consist of us utilizing how many combinations we had calculated for the left and right subtrees to derive a new answer within each iteration.
Let's start by creating our dp cache and setting our base cases for the first two subproblems.
If we have zero nodes, we would have only one combination of a structurally unique binary tree, since a null tree is considered valid.
If we have one node, then we would again only have one combination since we would have a tree that consists of a single node and no children.
dp = [0] * (n+1)
dp[0], dp[1] = 1, 1
Otherwise, we will begin tabulating.
Let's create our "expansion" loop, with the iterator i and this loop will traverse up to the nth number of nodes input. This is the loop that we will use to expand the range of our subproblem.
for i in range(2, n+1):
Next, we will create our "subproblem partition" loop with the iterator j and this loop will only focus on the subproblem partition between the first non-zero subproblem of the input array up to the index i is at, inclusively.
for j in range(1, i+1):
Within each iteration, we will continue calculating the combinations for the current subproblem of how many combinations we have for a binary search tree that contains i nodes.
To derive this, we will refer to the left and right subtrees.
Let's say, for example, we are looking for a subproblem of five nodes.
Our left and right subtrees respectively will be of length:
[0,4]
[1,3]
[2,2]
[3,1]
[4,0]
We can refer to these previously cached tree lengths and multiply them together to get each combination for the given subproblem of a tree with five nodes. We multiply these because the order of the nodes themselves can change within each subtree.
dp[i] += dp[j-1] * dp[i-j]
Once we have calculated each subproblem, the final subproblem will have been our answer.
return dp[-1]