# All Elements in Two Binary Search Trees
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/all-elements-in-two-binary-search-trees)
Canonical: https://scaleengineer.com/dsa/problems/all-elements-in-two-binary-search-trees
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting), [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search)
**Data structures:** Tree, Binary Tree, Binary Search Tree
---
## Problem
Given two binary search trees `root1` and `root2`, return _a list containing all the integers from both trees sorted in **ascending** order_.

**Example 1:**

![](https://assets.glich.co/dsa/all-elements-in-two-binary-search-trees/image0.png) 

**Input:** root1 = [2,1,4], root2 = [1,0,3]
**Output:** [0,1,1,2,3,4]

**Example 2:**

![](https://assets.glich.co/dsa/all-elements-in-two-binary-search-trees/image1.png) 

**Input:** root1 = [1,null,8], root2 = [8,1]
**Output:** [1,1,8,8]

**Constraints:**

* The number of nodes in each tree is in the range `[0, 5000]`.
* `-105 <= Node.val <= 105`

# Approaches
## Get All Elements and Sort
This is a straightforward brute-force approach. We first traverse both trees to collect all their node values into a single list. Then, we sort this combined list to get the final result. Any tree traversal method (pre-order, in-order, or post-order) can be used to collect the elements, as the order of collection does not matter before the final sort.
**Time:** O(M log M), where M = N1 + N2. Traversing both trees takes O(N1 + N2) time. Sorting the combined list of size M takes O(M log M) time. The sorting step is the dominant factor. · **Space:** O(N1 + N2). We need space to store all N1 + N2 elements in a list. Additionally, the recursion stack for traversal will take O(H1 + H2) space, where H1 and H2 are the heights of the trees. In the worst case (skewed trees), this is O(N1 + N2).
**Pros:** Very simple to conceptualize and implement.
**Cons:** This approach is inefficient as it does not leverage the fact that the input trees are Binary Search Trees (BSTs).; The time complexity is dominated by the sorting step, which is slower than linear time.
### Explanation
The core idea is to treat the trees as simple collections of numbers, ignoring their BST structure initially. 

1.  **Initialization**: We start by creating a dynamic array or list, let's call it `elements`, to hold all the integers from both trees.
2.  **Data Collection**: We perform a traversal on the first tree, `root1`. For every node we visit, we add its value to the `elements` list. We repeat the same process for the second tree, `root2`. After this step, `elements` contains all values from both trees, but in an unsorted order.
3.  **Sorting**: We apply a standard sorting algorithm to the `elements` list. Most programming languages provide a built-in sort function that is typically implemented with an efficient algorithm like Timsort or Quicksort.
4.  **Return**: The now-sorted `elements` list is the final result.

```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Integer> getAllElements(TreeNode root1, TreeNode root2) {
        List<Integer> list = new ArrayList<>();
        // Step 1 & 2: Traverse both trees and collect all elements
        collectElements(root1, list);
        collectElements(root2, list);
        
        // Step 3: Sort the combined list
        Collections.sort(list);
        
        // Step 4: Return the sorted list
        return list;
    }
    
    private void collectElements(TreeNode node, List<Integer> list) {
        if (node == null) {
            return;
        }
        list.add(node.val);
        collectElements(node.left, list);
        collectElements(node.right, list);
    }
}
```
### Algorithm
- Create an empty list `list`.
- Define a recursive helper function `collectElements` that takes a `TreeNode` and the list. If the node is not null, it adds the node's value to the list and recursively calls itself for the left and right children.
- Call `collectElements` for `root1` to add all its elements to `list`.
- Call `collectElements` for `root2` to add all its elements to `list`.
- Use a standard library function (e.g., `Collections.sort()`) to sort `list`.
- Return the sorted `list`.

## In-order Traversal and Merge
This approach leverages the key property of a Binary Search Tree (BST): an in-order traversal visits the nodes in ascending order. We perform an in-order traversal on each tree to get two separate sorted lists. Then, we merge these two sorted lists into a single sorted list, which is a much faster operation than a general-purpose sort.
**Time:** O(N1 + N2). The in-order traversal of `root1` takes O(N1) time, and for `root2` it takes O(N2) time. Merging the two sorted lists of sizes N1 and N2 is a linear operation that takes O(N1 + N2) time. Thus, the total time complexity is linear. · **Space:** O(N1 + N2). We need O(N1) space for `list1`, O(N2) for `list2`, and O(N1 + N2) for the result list. The recursion stack for the in-order traversals also takes O(H1 + H2) space.
**Pros:** Achieves a linear time complexity, which is a significant improvement over the sorting-based approach.; The logic is still relatively easy to follow: get two sorted lists and merge them.
**Cons:** Requires extra space to store the two intermediate sorted lists before merging them.
### Explanation
This method is more efficient because it takes advantage of the BST property.

1.  **In-order Traversal**: We define a recursive `inorder` helper function. This function traverses a tree by first visiting the left subtree, then the node itself, and finally the right subtree. We call this function on `root1` to populate a list, `list1`, and on `root2` to populate another list, `list2`. Because of the in-order traversal on BSTs, both `list1` and `list2` will be sorted.
2.  **Merge Sorted Lists**: We then merge `list1` and `list2` into a final `result` list. This is done using a standard two-pointer technique. We initialize a pointer for each list at the beginning. In a loop, we compare the elements at the current pointers, add the smaller element to `result`, and advance the pointer of the list from which the element was taken. This continues until one list is fully traversed. Finally, we append any remaining elements from the other list to `result`.

```java
class Solution {
    public List<Integer> getAllElements(TreeNode root1, TreeNode root2) {
        List<Integer> list1 = new ArrayList<>();
        inorder(root1, list1);
        
        List<Integer> list2 = new ArrayList<>();
        inorder(root2, list2);
        
        return merge(list1, list2);
    }
    
    private void inorder(TreeNode node, List<Integer> list) {
        if (node == null) {
            return;
        }
        inorder(node.left, list);
        list.add(node.val);
        inorder(node.right, list);
    }
    
    private List<Integer> merge(List<Integer> list1, List<Integer> list2) {
        List<Integer> result = new ArrayList<>();
        int p1 = 0, p2 = 0;
        
        while (p1 < list1.size() && p2 < list2.size()) {
            if (list1.get(p1) < list2.get(p2)) {
                result.add(list1.get(p1++));
            } else {
                result.add(list2.get(p2++));
            }
        }
        
        while (p1 < list1.size()) {
            result.add(list1.get(p1++));
        }
        
        while (p2 < list2.size()) {
            result.add(list2.get(p2++));
        }
        
        return result;
    }
}
```
### Algorithm
- Create two empty lists, `list1` and `list2`.
- Perform an in-order traversal on `root1` and store the resulting sorted elements in `list1`.
- Perform an in-order traversal on `root2` and store the resulting sorted elements in `list2`.
- Create an empty result list `result`.
- Use a two-pointer approach to merge the two sorted lists (`list1` and `list2`) into the `result` list.
- Return `result`.

## One-Pass Iterative In-order Traversal
This is the most optimal approach in terms of auxiliary space. Instead of generating the full sorted lists first, we can generate the elements from each tree one by one in sorted order and merge them on the fly. This is achieved by using two stacks to perform an iterative in-order traversal on both trees simultaneously, effectively treating the two traversals as sorted streams to be merged.
**Time:** O(N1 + N2). Each node from both trees is pushed onto and popped from a stack exactly once. The process is linear with respect to the total number of nodes. · **Space:** O(H1 + H2) for auxiliary space. The space is dominated by the two stacks. In the worst case of skewed trees, the heights H1 and H2 can be N1 and N2, making the space O(N1 + N2). However, for balanced trees, the space is O(log N1 + log N2). The output list itself requires O(N1 + N2) space.
**Pros:** Optimal time complexity of O(N1 + N2).; Optimal auxiliary space complexity of O(H1 + H2), which is better than O(N1 + N2) for balanced or moderately balanced trees.
**Cons:** The implementation is more complex and less intuitive than the previous approaches.
### Explanation
This approach simulates the in-order traversal iteratively for both trees at the same time and merges their outputs in a single pass.

1.  **Initialization**: We use two stacks, `s1` and `s2`, to manage the traversal for `root1` and `root2`, respectively. We also have an empty `result` list.
2.  **Simultaneous Traversal and Merge**: The main loop runs as long as either stack is non-empty or we still have nodes to visit in either tree. In each iteration:
    a.  We push the path to the smallest unvisited node of the current subtree onto the stack. For `root1`, we keep pushing `root1` to `s1` and moving `root1 = root1.left` until `root1` is null. We do the same for `root2` and `s2`.
    b.  Now, the top of `s1` and `s2` hold the next nodes in the in-order sequence for their respective trees. We compare their values.
    c.  We pick the node with the smaller value. Let's say `s1.peek().val` is smaller. We pop this node from `s1`, add its value to `result`, and then set our current node pointer for the first tree to the popped node's right child. This is crucial because the next elements in the sequence are in the right subtree.
    d.  If `s2.peek().val` was smaller (or if `s1` was empty), we would do the same for `s2`.
3.  This process continues until both trees are fully traversed, and the `result` list will contain all elements in sorted order.

```java
class Solution {
    public List<Integer> getAllElements(TreeNode root1, TreeNode root2) {
        List<Integer> result = new ArrayList<>();
        Stack<TreeNode> stack1 = new Stack<>();
        Stack<TreeNode> stack2 = new Stack<>();

        while (root1 != null || root2 != null || !stack1.isEmpty() || !stack2.isEmpty()) {
            // Go to the leftmost node in the current subtree for both trees
            while (root1 != null) {
                stack1.push(root1);
                root1 = root1.left;
            }
            while (root2 != null) {
                stack2.push(root2);
                root2 = root2.left;
            }

            // Compare the top elements of the stacks
            // If stack2 is empty or stack1's top is smaller/equal, process stack1
            if (stack2.isEmpty() || (!stack1.isEmpty() && stack1.peek().val <= stack2.peek().val)) {
                root1 = stack1.pop();
                result.add(root1.val);
                root1 = root1.right; // Move to the right subtree to find the next element
            } else { // Otherwise, process stack2
                root2 = stack2.pop();
                result.add(root2.val);
                root2 = root2.right; // Move to the right subtree
            }
        }
        return result;
    }
}
```
### Algorithm
- Initialize an empty result list `result` and two empty stacks, `stack1` and `stack2`.
- Start a loop that continues as long as there are nodes to process in either tree (either stack is not empty or a current node pointer is not null).
- Inside the loop, for each tree, traverse as far left as possible from the current node, pushing each node onto its corresponding stack.
- After attempting to go left, compare the values of the nodes at the top of `stack1` and `stack2`.
- If `stack2` is empty or `stack1`'s top element is smaller or equal, pop from `stack1`, add its value to `result`, and set the current node pointer for the first tree to the popped node's right child.
- Otherwise, do the same for `stack2`.
- Repeat until all nodes from both trees have been processed.
- Return `result`.

# Solutions
### Java

```java
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public List < Integer > getAllElements ( TreeNode root1 , TreeNode root2 ) { List < Integer > t1 = new ArrayList <>(); List < Integer > t2 = new ArrayList <>(); dfs ( root1 , t1 ); dfs ( root2 , t2 ); return merge ( t1 , t2 ); } private void dfs ( TreeNode root , List < Integer > t ) { if ( root == null ) { return ; } dfs ( root . left , t ); t . add ( root . val ); dfs ( root . right , t ); } private List < Integer > merge ( List < Integer > t1 , List < Integer > t2 ) { List < Integer > ans = new ArrayList <>(); int i = 0 , j = 0 ; while ( i < t1 . size () && j < t2 . size ()) { if ( t1 . get ( i ) <= t2 . get ( j )) { ans . add ( t1 . get ( i ++)); } else { ans . add ( t2 . get ( j ++)); } } while ( i < t1 . size ()) { ans . add ( t1 . get ( i ++)); } while ( j < t2 . size ()) { ans . add ( t2 . get ( j ++)); } return ans ; } }
```

### CPP

```cpp
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: vector < int > getAllElements ( TreeNode * root1 , TreeNode * root2 ) { vector < int > t1 ; vector < int > t2 ; dfs ( root1 , t1 ); dfs ( root2 , t2 ); return merge ( t1 , t2 ); } void dfs ( TreeNode * root , vector < int >& t ) { if ( ! root ) return ; dfs ( root -> left , t ); t . push_back ( root -> val ); dfs ( root -> right , t ); } vector < int > merge ( vector < int >& t1 , vector < int >& t2 ) { vector < int > ans ; int i = 0 , j = 0 ; while ( i < t1 . size () && j < t2 . size ()) { if ( t1 [ i ] <= t2 [ j ]) ans . push_back ( t1 [ i ++ ]); else ans . push_back ( t2 [ j ++ ]); } while ( i < t1 . size ()) ans . push_back ( t1 [ i ++ ]); while ( j < t2 . size ()) ans . push_back ( t2 [ j ++ ]); return ans ; } };
```

### Python

```python
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution : def getAllElements ( self , root1 : TreeNode , root2 : TreeNode ) -> List [ int ]: def dfs ( root , t ): if root is None : return dfs ( root . left , t ) t . append ( root . val ) dfs ( root . right , t ) def merge ( t1 , t2 ): ans = [] i = j = 0 while i < len ( t1 ) and j < len ( t2 ): if t1 [ i ] <= t2 [ j ]: ans . append ( t1 [ i ]) i += 1 else : ans . append ( t2 [ j ]) j += 1 while i < len ( t1 ): ans . append ( t1 [ i ]) i += 1 while j < len ( t2 ): ans . append ( t2 [ j ]) j += 1 return ans t1 , t2 = [], [] dfs ( root1 , t1 ) dfs ( root2 , t2 ) return merge ( t1 , t2 )
```