95. Unique Binary Search Trees II LeetCode Solution
In this guide, you will get 95. Unique Binary Search Trees II LeetCode Solution with the best time and space complexity. The solution to Unique Binary Search Trees II problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Unique Binary Search Trees II
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
Complexity Analysis
Time Complexity: O(3^n)
Space Complexity: O(3^n)
95. Unique Binary Search Trees II LeetCode Solution in C++
class Solution {
public:
vector<TreeNode*> generateTrees(int n) {
if (n == 0)
return {};
return generateTrees(1, n);
}
private:
vector<TreeNode*> generateTrees(int min, int max) {
if (min > max)
return {nullptr};
vector<TreeNode*> ans;
for (int i = min; i <= max; ++i)
for (TreeNode* left : generateTrees(min, i - 1))
for (TreeNode* right : generateTrees(i + 1, max)) {
ans.push_back(new TreeNode(i));
ans.back()->left = left;
ans.back()->right = right;
}
return ans;
}
}; /* code provided by PROGIEZ */
95. Unique Binary Search Trees II LeetCode Solution in Java
class Solution {
public List<TreeNode> generateTrees(int n) {
if (n == 0)
return new ArrayList<>();
return generateTrees(1, n);
}
private List<TreeNode> generateTrees(int mn, int mx) {
if (mn > mx)
return Arrays.asList((TreeNode) null);
List<TreeNode> ans = new ArrayList<>();
for (int i = mn; i <= mx; ++i)
for (TreeNode left : generateTrees(mn, i - 1))
for (TreeNode right : generateTrees(i + 1, mx)) {
ans.add(new TreeNode(i));
ans.get(ans.size() - 1).left = left;
ans.get(ans.size() - 1).right = right;
}
return ans;
}
} // code provided by PROGIEZ
95. Unique Binary Search Trees II LeetCode Solution in Python
class Solution:
def generateTrees(self, n: int) -> list[TreeNode]:
if n == 0:
return []
def generateTrees(mn: int, mx: int) -> list[int | None]:
if mn > mx:
return [None]
ans = []
for i in range(mn, mx + 1):
for left in generateTrees(mn, i - 1):
for right in generateTrees(i + 1, mx):
ans.append(TreeNode(i))
ans[-1].left = left
ans[-1].right = right
return ans
return generateTrees(1, n) # code by PROGIEZ
