1305. 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 = [0,-10,10], root2 = [5,1,7,0,2]
Output: [-10,0,0,1,2,5,7,10]

Example 3:

Input: root1 = [], root2 = [5,1,7,0,2]
Output: [0,1,2,5,7]

Example 4:

Input: root1 = [0,-10,10], root2 = []
Output: [-10,0,10]

Example 5:

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

Constraints:

----

Intuition

BST's inOrder is ascending

Traverse both trees leftMost first to get to start point of both, save nodes in a stack

while any of the stack is not empty

pick up the non empty stack

or pick the stack with lower peek value

add node.val to ans

Traverse leftmost on node.right

---

Time - O(M + N)

Space - O(M + 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) {
	List<Integer> ans = new ArrayList<Integer>();

	if (root1 == null && root2 == null) {
	return ans;
	}

	Stack<TreeNode> stack1 = new Stack<TreeNode>(), stack2 = new Stack<TreeNode>();

	pushLeft(root1, stack1);
	pushLeft(root2, stack2);

	while (!stack1.isEmpty() \|\| !stack2.isEmpty()) {
	Stack<TreeNode> st;
	if (stack1.isEmpty()) {
	st = stack2;
	} else if (stack2.isEmpty()) {
	st = stack1;
	} else {
	st = stack1.peek().val <= stack2.peek().val ? stack1 : stack2;
	}

	TreeNode node = st.pop();
	ans.add(node.val);
	pushLeft(node.right, st);
	}

	return ans;
	}

	private void pushLeft(TreeNode node, Stack<TreeNode> stack) {
	while (node != null) {
	stack.push(node);
	node = node.left;
	}
	}
	}

SWE Interview preparation