All Elements in Two Binary Search Trees LeetCode solution in Java

1
class Solution {
2
  public List<Integer> getAllElements(TreeNode root1, TreeNode root2) {
3
    Stack<TreeNode> st1 = new Stack<>();
4
    Stack<TreeNode> st2 = new Stack<>();
5

6
    List<Integer> res = new ArrayList<>();
7

8
    while (root1 != null || root2 != null || !st1.empty() || !st2.empty()) {
9
      while (root1 != null) {
10
        st1.push(root1);
11
        root1 = root1.left;
12
      }
13
      while (root2 != null) {
14
        st2.push(root2);
15
        root2 = root2.left;
16
      }
17
      if (st2.empty() || (!st1.empty() && st1.peek().val <= st2.peek().val)) {
18
        root1 = st1.pop();
19
        res.add(root1.val);
20
        root1 = root1.right;
21
      } else {
22
        root2 = st2.pop();
23
        res.add(root2.val);
24
        root2 = root2.right;
25
      }
26
    }
27
    return res;
28
  }
29
}