grid47 Exploring patterns and algorithms
Oct 28, 2024
6 min read
Solution to LeetCode 95: Unique Binary Search Trees II Problem
Given an integer n, return all structurally unique binary search trees (BSTs) that can be constructed using the integers from 1 to n. Each tree should be a unique arrangement of nodes where each node contains a unique value from the set {1, 2, …, n}.
Problem
Approach
Steps
Complexity
Input: The input is a single integer n, where 1 <= n <= 8, representing the number of nodes in the binary search tree.
Example: Input: n = 3
Constraints:
• 1 <= n <= 8
Output: Return a list of all structurally unique binary search trees that can be constructed using the integers from 1 to n. The output trees should be returned in any order.
• The output must include all unique BSTs without duplicates.
Goal: The goal is to generate all possible unique BSTs for a given number n, where each BST is formed by placing integers 1 to n as nodes in a valid binary search tree structure.
Steps:
• Recursively fix a root node and divide the remaining numbers into left and right subtrees.
• Generate all possible left and right subtrees for each choice of root node.
• Combine each left and right subtree with the current root and add them to the result list.
Goal: The problem assumes that the input is within the given range and that all tree structures should be returned in valid BST format.
Steps:
• 1 <= n <= 8
• Each node must have a unique value from the set {1, 2, ..., n}.
• The output must contain all structurally unique BSTs, not just one possible arrangement.
Assumptions:
• The input number n is valid and within the specified range.
• The binary search tree properties (left children < root and right children > root) must hold for all trees.
• Input: Input: n = 3
• Explanation: For n = 3, the unique BSTs can be formed by choosing each number as the root once, and then generating the corresponding left and right subtrees. The output consists of 5 unique BSTs.
• Input: Input: n = 1
• Explanation: For n = 1, there is only one possible BST: a single node tree with value 1.
Approach: To generate all unique BSTs for a given n, we can recursively fix a root and generate all possible left and right subtrees. We combine these subtrees to create the unique trees.
Observations:
• Binary search trees have unique properties, so each choice of root will generate different subtree configurations.
• We can approach this problem recursively by fixing a root, then recursively generating possible left and right subtrees for all numbers smaller and greater than the root.
• This problem requires a recursive strategy where we divide the problem into smaller subproblems by selecting a root and constructing the left and right subtrees for each choice.
Steps:
• For each integer i from 1 to n, treat i as the root node.
• Recursively generate all unique left subtrees for values less than i and all unique right subtrees for values greater than i.
• For each combination of left and right subtrees, create a new tree with i as the root and add it to the result.
Empty Inputs:
• If n = 0, there are no trees to generate.
Large Inputs:
• When n = 8, there are many possible unique BSTs to generate. Ensure the solution can handle the large number of trees efficiently.
Special Values:
• When n = 1, only one BST is possible, which is a single node tree.
Constraints:
• The solution should work efficiently for n values up to the maximum of 8.
vector<TreeNode*> run(int l, int r) {
vector<TreeNode*> ans, left, right;
if(l >= r) {
if(l == r) ans.push_back(new TreeNode(l));
else ans.push_back(NULL);
return ans;
}
for(int i = l; i <= r; i++) {
left = run(l, i -1);
right= run(i +1, r);
for(int j =0; j < left.size(); j++) {
for(int k =0; k < right.size(); k++) {
TreeNode* node =new TreeNode(i);
node->left = left[j];
node->right = right[k];
ans.push_back(node);
}
}
}
return ans;
}
vector<TreeNode*> generateTrees(int n) {
/*
This is a small light weight problem
my mind is not ready to think about this problem
bst is sorted array
we can fix a root and get a
array of left trees
and array of right trees
integrate them then add to result
*/ vector<TreeNode*> ans, left, right;
for(int i =1; i <= n; i++) {
left = run(1, i -1);
right= run(i +1, n);
for(int j =0; j < left.size(); j++) {
for(int k =0; k < right.size(); k++) {
TreeNode* node =new TreeNode(i);
node->left = left[j];
node->right = right[k];
ans.push_back(node);
}
}
}
return ans;
}
1 : Recursive Function
vector<TreeNode*> run(int l, int r) {
Defines a recursive function to generate trees for the range [l, r].
2 : Variable Initialization
vector<TreeNode*> ans, left, right;
Initializes vectors to store results, left subtrees, and right subtrees.
3 : Conditional Check
if(l >= r) {
Handles the base case where the range is invalid or a single node remains.
4 : Node Creation
if(l == r) ans.push_back(new TreeNode(l));
Creates a single node when l equals r and adds it to the results.
5 : Null Insertion
else ans.push_back(NULL);
Handles cases where there are no valid trees by adding a null tree.
6 : Return Statement
return ans;
Returns the generated trees for the current range.
7 : Loop Start
for(int i = l; i <= r; i++) {
Iterates through possible root values in the range [l, r].
8 : Recursive Call
left = run(l, i -1);
Recursively generates left subtrees for the current root.
9 : Recursive Call
right= run(i +1, r);
Recursively generates right subtrees for the current root.
10 : Nested Loop
for(int j =0; j < left.size(); j++) {
Iterates through all left subtrees.
11 : Nested Loop
for(int k =0; k < right.size(); k++) {
Iterates through all right subtrees.
12 : Node Creation
TreeNode* node =new TreeNode(i);
Creates a new root node with the current value.
13 : Tree Integration
node->left = left[j];
Attaches a left subtree to the root node.
14 : Tree Integration
node->right = right[k];
Attaches a right subtree to the root node.
15 : Result Addition
ans.push_back(node);
Adds the constructed tree to the results.
16 : Return Statement
return ans;
Returns the list of trees generated for the given range.
Best Case: O(2^n)
Average Case: O(2^n)
Worst Case: O(2^n)
Description: The time complexity is exponential, as we generate all possible BSTs for the given n.
Best Case: O(n)
Worst Case: O(n^2)
Description: The space complexity is O(n^2) in the worst case due to the recursion stack and storage for trees.
