All Elements in Two Binary Search Trees in Java

A binary search tree (BST) is a node-based data structure with two children, the left and right, allowing for efficient operations like searching, insertion, and deletion. However, combining or comparing elements from two BSTs is a common problem in applications like merging data, combining results, or synchronizing records. The goal is to return a list sorted in ascending order from both trees.

Example1:

Input

` root1 = [3,1,4], root2 = [2,1,5]`

Output: [1,1,2,3,4,5]

Explanation: root1 in-order traversal yields [1, 3, 4]; root2 in-order traversal yields [1, 2, 5]

Merged Sorted List: Combining [1, 3, 4] and [1, 2, 5] using a two-pointer merge results in [1, 1, 2, 3, 4, 5].

Example2:

Input:

`root1 = [10,5,15], root2 = [20,10,30]`

Output:  [5,10,10,15,20,30]

Explanation: root1 in-order traversal yields [5, 10, 15]; root2 in-order traversal yields [10, 20, 30]

Merged Sorted List: Combining [5, 10, 15] and [10, 20, 30] using a two-pointer merge results in [5, 10, 10, 15, 20, 30].

Using an In-order traversal and merge approach

Algorithm

Step 1: Perform in-order traversal on the first binary search tree to collect all elements in a sorted list.

Step 2: Perform in-order traversal on the second binary search tree to collect all elements in a sorted list.

Step 3: Initialize pointers i and j to 0, pointing to the start of list1 and list2.

Step 4: Create an empty list mergedList to store merged elements.

Step 5: Compare elements at list1[i] and list2[j], add a smaller element to mergedList, move the pointer forward, and add the remaining elements.

Step 6: Return mergedList, containing all elements from both binary search trees in sorted order.

Implementation

FileName:BSTElements.java

`import java.util.ArrayList;import java.util.List;class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int x) { val = x; }}public class BSTElements {public static void main(String[] args) {TreeNode root1 = new TreeNode(10);root1.left = new TreeNode(5);root1.right = new TreeNode(15);TreeNode root2 = new TreeNode(20);root2.left = new TreeNode(10);root2.right = new TreeNode(30);List<Integer> result = getAllElements(root1, root2);System.out.println(result);}public static List<Integer> getAllElements(TreeNode root1, TreeNode root2) {List<Integer> list1 = new ArrayList<>();List<Integer> list2 = new ArrayList<>();// In-order traversal of both treesinOrderTraversal(root1, list1);inOrderTraversal(root2, list2);// Merge the two sorted listsreturn mergeSortedLists(list1, list2);}private static void inOrderTraversal(TreeNode node, List<Integer> list) {if (node == null) return;inOrderTraversal(node.left, list);list.add(node.val);inOrderTraversal(node.right, list);}private static List<Integer> mergeSortedLists(List<Integer> list1, List<Integer> list2) {List<Integer> mergedList = new ArrayList<>();int i = 0, j = 0;// Merge the lists using two-pointer techniquewhile (i < list1.size() && j < list2.size()) {if (list1.get(i) < list2.get(j)) {mergedList.add(list1.get(i));i++;} else {mergedList.add(list2.get(j));j++;}}// Add remaining elementswhile (i < list1.size()) {mergedList.add(list1.get(i));i++;}while (j < list2.size()) {mergedList.add(list2.get(j));j++;}return mergedList;}}`

Output:

`[5, 10, 10, 15, 20, 30]`

Complexity analysis: The above approach has an overall time complexity of O(n1 + n2) due to in-order traversal and merging of sorted lists and overall  space complexity being O(n1 + n2) due to storage space for elements during traversal and merged list, and minimal extra space for variables and recursion stack frames.

Using Iterative In-order Traversal with a Merge approach

Algorithm

Step 1: Create an empty mergedList for merged elements.

Step 2: Create two stacks for iterative in-order traversal of root1 and root2.

Step 3: Use a helper function for in-order traversal and push nodes onto stacks.

Step 4: Compare top elements of stacks, pop smaller elements, and add to mergedList.

Step 5: Push the right child of the popped node back onto respective stacks.

Step 6: Handle remaining nodes, process and add to mergedList.

Step 7: Return mergedList, sorted elements from both binary search trees.

Implementation

FileName:BSTElements1.java

`import java.util.*;class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int x) { val = x; }}public class BSTElements1 {public static void main(String[] args) {TreeNode root1 = new TreeNode(10);root1.left = new TreeNode(5);root1.right = new TreeNode(15);TreeNode root2 = new TreeNode(20);root2.left = new TreeNode(10);root2.right = new TreeNode(30);List<Integer> result = getAllElements(root1, root2);System.out.println(result);}public static List<Integer> getAllElements(TreeNode root1, TreeNode root2) {List<Integer> mergedList = new ArrayList<>();Stack<TreeNode> stack1 = new Stack<>();Stack<TreeNode> stack2 = new Stack<>();// Perform iterative in-order traversal for root1pushLeftNodes(stack1, root1);// Perform iterative in-order traversal for root2pushLeftNodes(stack2, root2);// Merge process similar to merge step in merge sortwhile (!stack1.isEmpty() || !stack2.isEmpty()) {if (stack1.isEmpty()) {mergedList.add(stack2.peek().val);pushLeftNodes(stack2, stack2.pop().right);} else if (stack2.isEmpty()) {mergedList.add(stack1.peek().val);pushLeftNodes(stack1, stack1.pop().right);} else {if (stack1.peek().val < stack2.peek().val) {mergedList.add(stack1.peek().val);pushLeftNodes(stack1, stack1.pop().right);} else {mergedList.add(stack2.peek().val);pushLeftNodes(stack2, stack2.pop().right);}}}return mergedList;}// Helper method to push left nodes onto stackprivate static void pushLeftNodes(Stack<TreeNode> stack, TreeNode node) {while (node != null) {stack.push(node);node = node.left;}}}`

Output:

`[5, 10, 10, 15, 20, 30]`

Complexity analysis: The above approach has an overall time and space complexity of O(n1 + n2) due to iterative in-order traversal on `root1` and `root2` and the merging process of two sorted lists into `mergedList`. The space complexity is O(n1 + n2) due to stacks used for iterative traversal and `mergedList`, which stores all elements in sorted order.