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.
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 def inOrder(node):
10 return inOrder(node.left) + [node.val] + inOrder(node.right) if node else []
11
12 list1, list2 = inOrder(root1), inOrder(root2)
13 return sorted(list1 + list2)
14The Python solution uses an in-order traversal function that returns a list. By leveraging this function, we build sorted lists from both trees and concatenate them before returning the fully sorted list using Python's built-in sorted function.
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.
1import java.util.ArrayList;
2import java.util.List;
3import java.util.Stack;
4
5public class Solution {
6 public List<Integer> getAllElements(TreeNode root1, TreeNode root2) {
7 List<Integer> result = new ArrayList<>();
8 Stack<TreeNode> stack1 = new Stack<>();
9 Stack<TreeNode> stack2 = new Stack<>();
10 while (root1 != null || root2 != null || !stack1.isEmpty() || !stack2.isEmpty()) {
11 while (root1 != null) {
12 stack1.push(root1);
13 root1 = root1.left;
14 }
15 while (root2 != null) {
16 stack2.push(root2);
17 root2 = root2.left;
18 }
19 if (stack2.isEmpty() || (!stack1.isEmpty() && stack1.peek().val <= stack2.peek().val)) {
20 root1 = stack1.pop();
21 result.add(root1.val);
22 root1 = root1.right;
23 } else {
24 root2 = stack2.pop();
25 result.add(root2.val);
26 root2 = root2.right;
27 }
28 }
29 return result;
30 }
31
32 public static class TreeNode {
33 int val;
34 TreeNode left;
35 TreeNode right;
36 TreeNode(int x) { val = x; }
37 }
38}
39This Java implementation utilizes two stacks to iteratively perform an in-order traversal, which avoids recursion limitations and processes each node whenever its tree reaches a leaf. By popping from the stack with the smaller node, it guarantees ordered addition, efficiently managing space through finely scoped stack depth utilization.