This approach leverages the in-order traversal property of Binary Search Trees (BSTs), which yields elements in sorted order. We perform an in-order traversal on both trees to extract elements into separate lists. We then merge these two sorted lists into one sorted list.
Time Complexity: O(n + m) where n and m are the number of nodes in root1 and root2, respectively. Space Complexity: O(n + m) for storing the elements from both trees.
1#include <vector>
2#include <queue>
3using namespace std;
4
5struct TreeNode {
6 int val;
7 TreeNode *left;
8 TreeNode *right;
9 TreeNode(int x) : val(x), left(NULL), right(NULL) {}
10};
11
12void inOrder(TreeNode* root, vector<int>& result) {
13 if (!root) return;
14 inOrder(root->left, result);
15 result.push_back(root->val);
16 inOrder(root->right, result);
17}
18
19vector<int> mergeSortedLists(vector<int>& list1, vector<int>& list2) {
20 vector<int> merged;
21 int i = 0, j = 0;
22 while (i < list1.size() && j < list2.size()) {
23 if (list1[i] < list2[j])
24 merged.push_back(list1[i++]);
25 else
26 merged.push_back(list2[j++]);
27 }
28 while (i < list1.size())
29 merged.push_back(list1[i++]);
30 while (j < list2.size())
31 merged.push_back(list2[j++]);
32 return merged;
33}
34
35vector<int> getAllElements(TreeNode* root1, TreeNode* root2) {
36 vector<int> list1, list2;
37 inOrder(root1, list1);
38 inOrder(root2, list2);
39 return mergeSortedLists(list1, list2);
40}
41This C++ solution involves in-order traversal to retrieve sorted elements into two separate vectors. The vectors are then merged using a typical merging approach, yielding a final sorted vector which is returned.
This approach uses stacks to perform an iterative in-order traversal of both trees simultaneously. We make use of two separate stacks to store the nodes of current branches of the trees. The smallest node from the top of the stacks is chosen and processed to build the result list in sorted order.
Time Complexity: O(n + m) for processing all nodes, where n and m are the numbers of nodes in the two trees. Space Complexity: O(h1 + h2) where h1 and h2 are the heights of the two trees for the stack size.
1class TreeNode:
2 def __init__(self, x):
3 self.val = x
4 self.left = None
5 self.right = None
6
7class Solution:
8 def getAllElements(self, root1, root2):
9 stack1, stack2, result = [], [], []
10 while root1 or root2 or stack1 or stack2:
11 while root1:
12 stack1.append(root1)
13 root1 = root1.left
14 while root2:
15 stack2.append(root2)
16 root2 = root2.left
17
18 if not stack2 or (stack1 and stack1[-1].val <= (stack2[-1]).val):
19 root1 = stack1.pop()
20 result.append(root1.val)
21 root1 = root1.right
22 else:
23 root2 = stack2.pop()
24 result.append(root2.val)
25 root2 = root2.right
26 return result
27The Python approach operates using two stacks, simulating an in-order traversal without resorting to function-stack based recursion. This organizes traversals node by node, evaluating each tree's progression state to maintain consistently sorted final results with reactive in-scene processing efficiency.