###### tags: `LeetCode Study Group - Tree` `LeetCode Medium` `LeetCode Study Group` `Prep Again`
# 1305. All Elements in Two Binary Search Trees
Link: https://leetcode.com/problems/all-elements-in-two-binary-search-trees/description/

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

Time complexity: O(nlog n)
Space complexity: O(n)

/**
 * 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) {
        ArrayList<Integer> res = new ArrayList<Integer>();
        tree(root1, res);
        tree(root2, res);
        Collections.sort(res);
        return res;
    }

    public void tree(TreeNode root, ArrayList<Integer> list){
        if(root == null)
           return;
        list.add(root.val);

        tree(root.left, list);
        tree(root.right, list);

    }
}

## Solution-2

Time complexity: O(n + m)
Space complexity: O(n + m)

/**
 * 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) {
         ArrayList<Integer> res = new ArrayList<Integer>();
        Stack<TreeNode> stack1 = new Stack();
        Stack<TreeNode> stack2 = new Stack();
        
        while(root1 != null || root2 != null || 
              !stack1.empty() || !stack2.empty()) {

              while(root1 != null) {
                  stack1.push(root1);
                  root1 = root1.left;
              }

               while(root2 != null) {
                  stack2.push(root2);
                  root2 = root2.left;
              }


              if(stack2.empty() || (!stack1.empty() && stack1.peek().val <= stack2.peek().val)) {
                  root1 = stack1.pop();
                  res.add(root1.val);
                  root1 = root1.right;
              }else{
                  root2 = stack2.pop();
                  res.add(root2.val);
                  root2 = root2.right;
              }
             
        }
        
        return res;
    }
}

## Reference
https://leetcode.com/problems/all-elements-in-two-binary-search-trees/solutions/1720210/java-c-python-a-very-very-detailed-explanation/

https://leetcode.com/problems/all-elements-in-two-binary-search-trees/solutions/1719941/c-best-explanation-naive-and-optimal/