132. Merge Two BSTs Into One

Given two binary search trees, combine all of their values into a single sorted sequence and print it, space-separated (duplicate values across the two trees are both kept). Each tree is given as its own line of level-order tokens (the shared level-order/'N' convention from other BST problems applies to both).

Input: Two lines, each a space-separated level-order token representation ('N' for missing children) of a binary search tree - one tree per line. Output: Print a single sorted sequence combining every value from both trees, space-separated on one line (duplicates across the two trees are both kept).

1 <= number of nodes in each tree <= 10^5

Duplicate values across the two trees are explicitly KEPT (not deduplicated) per this problem's statement - a simple merge naturally preserves this, unlike a 'union' operation which would need explicit deduplication.

Combine the values from two separate binary search trees into one single sorted sequence. Brute force: Combine both trees' values into one big list and run a general-purpose sort on the whole thing - this works but costs O((n1+n2) log(n1+n2)), ignoring that both individual traversals are already sorted. Optimised: Since each tree's inorder traversal is already sorted individually, a simple two-pointer merge (the same technique as merging two sorted arrays) combines them in linear time - no need to re-sort information that's already sorted within each source.

Do an inorder traversal of each BST into its own array, which - because inorder traversal of a BST always visits values in ascending order - produces two already-sorted arrays. Then merge those two sorted arrays with the standard two-pointer merge technique (advance whichever pointer currently points to the smaller value, appending it to the output) instead of re-sorting the combined data. This exploits the sortedness the brute-force approach ignored, dropping the logarithmic factor entirely. Time: O(n1+n2) Space: O(n1+n2)

Instead of fully materializing both trees into arrays before merging, drive two independent iterative inorder traversals (each using its own explicit stack) side by side, one per tree. At each step, peek at both traversals' current values, advance whichever one is smaller and output its value (advancing the other on a tie so both duplicates are emitted), continuing until both stacks are exhausted. This produces the final merged sequence in the same single logical pass as the better approach, but never stores a full array for either tree - only the two traversal stacks, each bounded by the corresponding tree's height - so extra memory scales with tree height rather than tree size. Time: O(n1+n2) Space: O(h1+h2)

Do an inorder traversal of the first tree into array1 and an inorder traversal of the second tree into array2 (each takes O(n) time), then concatenate them into one combined array and run a general-purpose sort over the whole thing before printing it. This is correct but throws away the fact that array1 and array2 are each already individually sorted by construction, paying an unnecessary logarithmic sorting factor over the combined size. Time: O((n1+n2) log(n1+n2)) Space: O(n1+n2)

1. Get the inorder traversal of EACH tree separately - since each is a BST, both are already individually sorted. 2. Merge the two sorted sequences together, exactly like the classic 'merge two sorted arrays' two-pointer technique. 3. Print the fully merged, combined sorted sequence.

Time: O(n1 + n2) - one traversal per tree, plus a linear merge pass. Space: O(n1 + n2), for the two collected sorted sequences and the merged result.

Test two single-node trees, trees that share a duplicate value (both copies must appear), and each tree's size approaching 10^5 nodes for performance.

Be ready to connect this directly to 'Merge Two Sorted Arrays' - the entire technique is identical, just with the sorted sequences coming from BST inorder traversals instead of already-given arrays.