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
![All Elements in Two Binary Search Trees in Java](https://static.tutorialandexample.com/java/all-elements-in-two-binary-search-trees-in-java1.png)
![All Elements in Two Binary Search Trees in Java](https://static.tutorialandexample.com/java/all-elements-in-two-binary-search-trees-in-java2.png)
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:
![All Elements in Two Binary Search Trees in Java](https://static.tutorialandexample.com/java/all-elements-in-two-binary-search-trees-in-java3.png)
![All Elements in Two Binary Search Trees in Java](https://static.tutorialandexample.com/java/all-elements-in-two-binary-search-trees-in-java4.png)
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); Listresult = getAllElements(root1, root2); System.out.println(result); } public static List getAllElements(TreeNode root1, TreeNode root2) { List list1 = new ArrayList<>(); List list2 = new ArrayList<>(); // In-order traversal of both trees inOrderTraversal(root1, list1); inOrderTraversal(root2, list2); // Merge the two sorted lists return mergeSortedLists(list1, list2); } private static void inOrderTraversal(TreeNode node, List list) { if (node == null) return; inOrderTraversal(node.left, list); list.add(node.val); inOrderTraversal(node.right, list); } private static List mergeSortedLists(List list1, List list2) { List mergedList = new ArrayList<>(); int i = 0, j = 0; // Merge the lists using two-pointer technique while (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 elements while (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); Listresult = getAllElements(root1, root2); System.out.println(result); } public static List getAllElements(TreeNode root1, TreeNode root2) { List mergedList = new ArrayList<>(); Stack stack1 = new Stack<>(); Stack stack2 = new Stack<>(); // Perform iterative in-order traversal for root1 pushLeftNodes(stack1, root1); // Perform iterative in-order traversal for root2 pushLeftNodes(stack2, root2); // Merge process similar to merge step in merge sort while (!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 stack private static void pushLeftNodes(Stack 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.