All Elements in Two Binary Search Trees

Each BST yields sorted values under in-order traversal, so merge the two traversals like two sorted arrays. Maintain two stacks; a helper pushes a node and all of its left descendants. Initialize each stack with its tree's left spine. The top of each nonempty stack is that tree's next smallest value. Pop the smaller top, append its value, then push the left spine of its right child into the same stack. If one stack is empty, consume the other. This avoids storing two full traversals before merging. Every node is pushed and popped once, giving O(n plus m) time. The stacks use O(h1 plus h2) auxiliary space, excluding the O(n plus m) output. A simple alternative collects both in-order arrays then merges them, but it uses unnecessary extra memory.