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.
1using System;
2using System.Collections.Generic;
3
4public class TreeNode {
5 public int val;
6 public TreeNode left;
7 public TreeNode right;
8 public TreeNode(int x) { val = x; }
9}
10
11public class Solution {
12 public IList<int> GetAllElements(TreeNode root1, TreeNode root2) {
13 List<int> list1 = new List<int>();
14 List<int> list2 = new List<int>();
15 InOrder(root1, list1);
16 InOrder(root2, list2);
17 return MergeSortedLists(list1, list2);
18 }
19
20 private void InOrder(TreeNode node, List<int> list) {
21 if (node == null) return;
22 InOrder(node.left, list);
23 list.Add(node.val);
24 InOrder(node.right, list);
25 }
26
27 private List<int> MergeSortedLists(List<int> list1, List<int> list2) {
28 List<int> merged = new List<int>();
29 int i = 0, j = 0;
30 while (i < list1.Count && j < list2.Count) {
31 if (list1[i] < list2[j])
32 merged.Add(list1[i++]);
33 else
34 merged.Add(list2[j++]);
35 }
36 while (i < list1.Count)
37 merged.Add(list1[i++]);
38 while (j < list2.Count)
39 merged.Add(list2[j++]);
40 return merged;
41 }
42}
43C# solution employs in-order traversal to collect elements from two binary search trees into lists. These lists are then merged into one sorted list which is returned to the caller.
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.
1function TreeNode(val, left = null, right = null) {
2 this.val = (val===undefined ? 0 : val)
3 this.left = (left===undefined ? null : left)
4 this.right = (right===undefined ? null : right)
5}
6
7var getAllElements = function(root1, root2) {
8 let stack1 = [], stack2 = [], result = [];
9
10 while (root1 || root2 || stack1.length > 0 || stack2.length > 0) {
11 while (root1) {
12 stack1.push(root1);
13 root1 = root1.left;
14 }
15 while (root2) {
16 stack2.push(root2);
17 root2 = root2.left;
18 }
19
20 let val1 = (!stack1.length) ? Number.MAX_SAFE_INTEGER : stack1[stack1.length-1].val;
21 let val2 = (!stack2.length) ? Number.MAX_SAFE_INTEGER : stack2[stack2.length-1].val;
22
23 if (val1 <= val2) {
24 root1 = stack1.pop();
25 result.push(root1.val);
26 root1 = root1.right;
27 } else {
28 root2 = stack2.pop();
29 result.push(root2.val);
30 root2 = root2.right;
31 }
32 }
33
34 return result;
35};
36The JavaScript solution adapts iterative two-stack traversal, coalescing both binary tree node sequences by handling dual stack comparisons. The out-of-call-stack approach facilitates an overlap-resistant node processing order that builds a final sorted array with consistent attention to element precedence.