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 <stdio.h>
2#include <stdlib.h>
3
4typedef struct TreeNode {
5 int val;
6 struct TreeNode *left;
7 struct TreeNode *right;
8} TreeNode;
9
10void inOrder(TreeNode* root, int* arr, int* returnSize) {
11 if (root == NULL)
12 return;
13 inOrder(root->left, arr, returnSize);
14 arr[(*returnSize)++] = root->val;
15 inOrder(root->right, arr, returnSize);
16}
17
18int* merge(int* list1, int size1, int* list2, int size2, int* returnSize) {
19 int* result = (int*)malloc((size1 + size2) * sizeof(int));
20 *returnSize = 0;
21 int i = 0, j = 0;
22 while (i < size1 && j < size2) {
23 if (list1[i] < list2[j])
24 result[(*returnSize)++] = list1[i++];
25 else
26 result[(*returnSize)++] = list2[j++];
27 }
28 while (i < size1)
29 result[(*returnSize)++] = list1[i++];
30 while (j < size2)
31 result[(*returnSize)++] = list2[j++];
32 return result;
33}
34
35int* getAllElements(TreeNode* root1, TreeNode* root2, int* returnSize) {
36 int list1[5000], list2[5000];
37 int size1 = 0, size2 = 0;
38 inOrder(root1, list1, &size1);
39 inOrder(root2, list2, &size2);
40 return merge(list1, size1, list2, size2, returnSize);
41}
42The C solution uses two utility functions: inOrder, which performs an in-order traversal of a tree, and merge, which merges two sorted arrays. After gathering all elements from both trees using in-order traversal, the resulting arrays are merged to form a single sorted array, 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.
1#include <vector>
2#include <stack>
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
12vector<int> getAllElements(TreeNode* root1, TreeNode* root2) {
13 vector<int> result;
14 stack<TreeNode*> s1, s2;
15 while (root1 || root2 || !s1.empty() || !s2.empty()) {
16 while (root1) {
17 s1.push(root1);
18 root1 = root1->left;
19 }
20 while (root2) {
21 s2.push(root2);
22 root2 = root2->left;
23 }
24
25 if (s2.empty() || (!s1.empty() && s1.top()->val <= s2.top()->val)) {
26 root1 = s1.top(); s1.pop();
27 result.push_back(root1->val);
28 root1 = root1->right;
29 } else {
30 root2 = s2.top(); s2.pop();
31 result.push_back(root2->val);
32 root2 = root2->right;
33 }
34 }
35 return result;
36}
37The C++ solution illustrates an iterative in-order traversal with two stacks. Each tree's nodes are pushed onto its respective stack, only to pop and process the smallest. This effectively orders nodes by value, producing a merged sorted sequence, minimizing space usage to maintain stacks only as deep as the trees' heights.