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.
1import java.util.ArrayList;
2import java.util.List;
3
4public class Solution {
5 public List<Integer> getAllElements(TreeNode root1, TreeNode root2) {
6 List<Integer> list1 = new ArrayList<>();
7 List<Integer> list2 = new ArrayList<>();
8 inOrder(root1, list1);
9 inOrder(root2, list2);
10 return mergeSortedLists(list1, list2);
11 }
12
13 private void inOrder(TreeNode root, List<Integer> list) {
14 if (root == null) return;
15 inOrder(root.left, list);
16 list.add(root.val);
17 inOrder(root.right, list);
18 }
19
20 private List<Integer> mergeSortedLists(List<Integer> list1, List<Integer> list2) {
21 List<Integer> merged = new ArrayList<>();
22 int i = 0, j = 0;
23 while (i < list1.size() && j < list2.size()) {
24 if (list1.get(i) < list2.get(j))
25 merged.add(list1.get(i++));
26 else
27 merged.add(list2.get(j++));
28 }
29 while (i < list1.size())
30 merged.add(list1.get(i++));
31 while (j < list2.size())
32 merged.add(list2.get(j++));
33 return merged;
34 }
35
36 public static class TreeNode {
37 int val;
38 TreeNode left;
39 TreeNode right;
40 TreeNode(int x) { val = x; }
41 }
42}
43This Java solution performs in-order traversal of both trees and stores the results in two lists. These sorted lists are merged into a final sorted list which is returned. This approach efficiently combines the elements with minimal additional space usage.
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 <stdio.h>
2#include <stdlib.h>
3
4typedef struct TreeNode {
5 int val;
6 struct TreeNode *left;
7 struct TreeNode *right;
8} TreeNode;
9
10typedef struct Stack {
11 TreeNode **arr;
12 int top;
13} Stack;
14
15Stack* createStack(int size) {
16 Stack *stack = (Stack *)malloc(sizeof(Stack));
17 stack->arr = (TreeNode **)malloc(size * sizeof(TreeNode *));
18 stack->top = -1;
19 return stack;
20}
21
22void push(Stack *stack, TreeNode *node) {
23 stack->arr[++stack->top] = node;
24}
25
26TreeNode* pop(Stack *stack) {
27 return stack->arr[stack->top--];
28}
29
30int isEmpty(Stack *stack) {
31 return stack->top == -1;
32}
33
34int* getAllElements(TreeNode* root1, TreeNode* root2, int* returnSize) {
35 int* result = (int *)malloc(10000 * sizeof(int));
36 *returnSize = 0;
37 Stack *stack1 = createStack(5000);
38 Stack *stack2 = createStack(5000);
39
40 while (root1 || root2 || !isEmpty(stack1) || !isEmpty(stack2)) {
41 while (root1) {
42 push(stack1, root1);
43 root1 = root1->left;
44 }
45 while (root2) {
46 push(stack2, root2);
47 root2 = root2->left;
48 }
49
50 if (isEmpty(stack2) || (!isEmpty(stack1) && stack1->arr[stack1->top]->val <= stack2->arr[stack2->top]->val)) {
51 root1 = pop(stack1);
52 result[(*returnSize)++] = root1->val;
53 root1 = root1->right;
54 } else {
55 root2 = pop(stack2);
56 result[(*returnSize)++] = root2->val;
57 root2 = root2->right;
58 }
59 }
60
61 free(stack1->arr);
62 free(stack1);
63 free(stack2->arr);
64 free(stack2);
65 return result;
66}
67The C solution implements iterative in-order traversal using stacks. It pushes nodes from both trees onto separate stacks. By comparing the top nodes' values from both stacks, the smaller is popped and its value is added to the result array. This continues until all nodes are processed. This approach efficiently combines elements just in time by always considering the smallest available node.