Leetcode 1305: All Elements in Two Binary Search Trees
Given two binary search trees, root1 and root2, return a list containing all the integers from both trees, sorted in ascending order.
Problem
Approach
Steps
Complexity
Input: Each tree is represented by its root node, and the nodes of the tree follow the binary search tree property where left child < parent node < right child.
Example: Input: root1 = [3, 1, 4], root2 = [2, 0, 5]
Constraints:
• The number of nodes in each tree is in the range [0, 5000].
• -105 <= Node.val <= 105
Output: Return a sorted list containing all the integers from both trees.
Example: Output: [0, 1, 2, 3, 4, 5]
Constraints:
• The output list will contain the sorted integers from both input trees.
Goal: To merge the two binary search trees and return the merged list of elements sorted in ascending order.
Steps:
• Use a two-pointer or stack-based approach to traverse both trees in in-order (left, root, right) fashion.
• Merge the results of both traversals and return the combined sorted list.
Goal: The solution must handle trees with up to 5000 nodes efficiently.
Steps:
• The number of nodes in each tree is between 0 and 5000.
• Node values are between -105 and 105.
Assumptions:
• Both trees are valid binary search trees.
• The solution should be efficient enough to handle trees with up to 5000 nodes.
• Input: Input: root1 = [3, 1, 4], root2 = [2, 0, 5]
• Explanation: The combined elements from both trees are [3, 1, 4] and [2, 0, 5]. Sorting these values gives [0, 1, 2, 3, 4, 5].
• Input: Input: root1 = [6, null, 10], root2 = [5, 2, 7]
• Explanation: The combined elements from both trees are [6, 10] and [5, 2, 7]. Sorting these values gives [2, 5, 6, 7, 10].
Approach: The best approach is to perform an in-order traversal of both trees and merge the results as they are traversed in sorted order.
Observations:
• Binary search trees store elements in sorted order. This allows us to merge the trees efficiently using in-order traversal.
• We can use stacks to simulate the in-order traversal of both trees, which will allow us to process both trees simultaneously.
Steps:
• Initialize two stacks, one for each tree, to simulate the in-order traversal.
• Push nodes into the stacks while traversing the left subtree of each tree.
• Once both stacks are populated, compare the top values of both stacks, pop the smaller value, and add it to the result list.
• Move to the right child of the node that was popped, repeating the process until both stacks are empty.
Empty Inputs:
• If one of the trees is empty, the solution should simply return the in-order traversal of the other tree.
Large Inputs:
• For very large trees, the solution should efficiently merge and sort the trees in linear time.
Special Values:
• If the trees contain duplicate values, the duplicates should appear in the result list in sorted order.
Constraints:
• The solution should operate within O(n) time complexity, where n is the total number of nodes across both trees.
vector<int> getAllElements(TreeNode* root1, TreeNode* root2) {
stack<TreeNode*> st1, st2;
vector<int> res;
while(root1 || root2 || !st1.empty() || !st2.empty()) {
while(root1) {
st1.push(root1);
root1 = root1->left;
}
while(root2) {
st2.push(root2);
root2 = root2->left;
}
if(st2.empty() || (!st1.empty() && st1.top()->val < st2.top()->val)) {
root1 = st1.top();
st1.pop();
res.push_back(root1->val);
root1 = root1->right;
} else {
root2 = st2.top();
st2.pop();
res.push_back(root2->val);
root2 = root2->right;
}
}
return res;
}
1 : Function Definition
vector<int> getAllElements(TreeNode* root1, TreeNode* root2) {
Defines the function 'getAllElements' that takes two root nodes of binary search trees (root1 and root2) as input and returns a vector of integers containing all elements from both trees, sorted in ascending order.
2 : Stack Initialization
stack<TreeNode*> st1, st2;
Declares two stacks, st1 and st2, to store nodes of both trees during the in-order traversal.
3 : Result Vector Initialization
vector<int> res;
Declares an empty vector 'res' that will hold the elements from both trees in sorted order.
4 : Main Loop
while(root1 || root2 || !st1.empty() || !st2.empty()) {
The while loop continues until both trees are fully traversed and both stacks are empty.
5 : Left Subtree Traversal - Root1
while(root1) {
Traverses the left subtree of tree 1, pushing all nodes onto the stack st1 until a NULL node is encountered.
6 : Push Root1 to Stack
st1.push(root1);
Pushes the current node (root1) onto the stack st1.
7 : Move to Left Child
root1 = root1->left;
Moves to the left child of the current node in tree 1.
8 : Left Subtree Traversal - Root2
while(root2) {
Traverses the left subtree of tree 2, pushing all nodes onto the stack st2 until a NULL node is encountered.
9 : Push Root2 to Stack
st2.push(root2);
Pushes the current node (root2) onto the stack st2.
10 : Move to Left Child
root2 = root2->left;
Moves to the left child of the current node in tree 2.
11 : Comparison and Node Selection
if(st2.empty() || (!st1.empty() && st1.top()->val < st2.top()->val)) {
Compares the top nodes of the stacks to decide which node to pop. If stack st2 is empty or the top node of st1 is smaller than the top node of st2, it selects the node from tree 1.
12 : Pop and Process Node from St1
root1 = st1.top();
Pops the top node from stack st1 and processes it.
13 : Pop from St1
st1.pop();
Removes the processed node from stack st1.
14 : Add Value to Result
res.push_back(root1->val);
Adds the value of the current node from tree 1 to the result vector.
15 : Move to Right Child - Root1
root1 = root1->right;
Moves to the right child of the current node in tree 1.
16 : Else Clause - Node Selection from St2
} else {
If the condition is false, it selects the node from tree 2 (either st2 is not empty or the top node of st2 is smaller).
17 : Pop and Process Node from St2
root2 = st2.top();
Pops the top node from stack st2 and processes it.
18 : Pop from St2
st2.pop();
Removes the processed node from stack st2.
19 : Add Value to Result
res.push_back(root2->val);
Adds the value of the current node from tree 2 to the result vector.
20 : Move to Right Child - Root2
root2 = root2->right;
Moves to the right child of the current node in tree 2.
21 : Return Result
return res;
Returns the sorted result vector containing all elements from both trees.
Best Case: O(n) - If both trees are balanced, the traversal and merging will take linear time.
Average Case: O(n) - The traversal and merging will always take linear time relative to the total number of nodes.
Worst Case: O(n) - The worst case occurs when the trees are skewed, but the time complexity remains linear in terms of node count.
Description: The time complexity is O(n), where n is the total number of nodes in both trees.
Best Case: O(h) - Even in the best case, the space complexity is determined by the height of the trees.
Worst Case: O(h) - The space complexity is O(h) where h is the height of the taller tree due to the stack space used during traversal.
Description: The space complexity is O(h), where h is the height of the taller tree.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus