top of page
Search

# All Elements in Two Binary Search Trees

Given two binary search trees root1 and root2, return a list containing all the integers from both trees sorted in ascending order.

Example 1:

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

Example 2:

```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

Solution:

```/**
* 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) {
Stack<TreeNode> s1 = new Stack<>();
Stack<TreeNode> s2 = new Stack<>();

List<Integer> result = new ArrayList<>();

while(root1!=null || root2!=null || !s1.empty() || !s2.empty()){
while(root1!=null)
{
s1.push(root1);
root1=root1.left;
}
while(root2!=null)
{
s2.push(root2);
root2=root2.left;
}
if(s2.empty() || (!s1.empty() && s1.peek().val <= s2.peek().val))
{
root1 = s1.pop();
root1 = root1.right;
}
else
{
root2 = s2.pop();
root2 = root2.right;
}

}

return result;
}
}

```