Similar Problems
Similar Problems not available
Unique Binary Search Trees - Leetcode Solution
Companies:
LeetCode: Unique Binary Search Trees Leetcode Solution
Difficulty: Medium
Topics: binary-search-tree dynamic-programming math tree binary-tree
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.
Solution approach: The problem can be solved using dynamic programming approach. The idea is to count the number of unique binary search trees that can be formed with n nodes.
To count the number of unique binary search trees, we can use the fact that each number from 1 to n can be the root of the BST. When i is the root of the BST, the left subtree will have i-1 nodes and the right subtree will have n-i nodes. We can use this fact to recursively count the number of unique BSTs that can be formed with i-1 nodes in the left subtree and n-i nodes in the right subtree.
To avoid calculating the same values multiple times, we can store the values in a memoization array and use them when needed.
Algorithm:
- Create a memoization array of size n+1 and initialize it with 0.
- memo[0] and memo[1] are initialized with 1 since there is only one way to form a BST with 0 or 1 nodes.
- For i from 2 to n+1, do the following: a. For j from 1 to i, do the following: i. memo[i] += memo[j-1]*memo[i-j]
- Return memo[n].
Explanation:
- Create a memoization array of size n+1 and initialize it with 0 to avoid calculating the same values multiple times.
- memo[0] and memo[1] are initialized with 1 since there is only one way to form a BST with 0 or 1 nodes.
- We loop from 2 to n+1 since we know that there must be at least 2 nodes to form a BST. We loop through j from 1 to i since j can be the root of the BST. For each j, we calculate the number of unique BSTs that can be formed with j-1 nodes in the left subtree and i-j nodes in the right subtree. We multiply these values and add it to memo[i] since we are counting the number of unique BSTs that can be formed with i nodes. At the end of the loop, memo[i] will contain the number of unique BSTs that can be formed with i nodes.
- We return memo[n] since we are interested in the number of unique BSTs that can be formed with n nodes.
Time complexity: O(n^2) Space complexity: O(n)
Solution code in Python:
class Solution: def numTrees(self, n: int) -> int: memo = [0]*(n+1) memo[0],memo[1] = 1,1 for i in range(2,n+1): for j in range(1,i+1): memo[i] += memo[j-1]*memo[i-j] return memo[n]
Unique Binary Search Trees Solution Code
1