PPractick

The problem

Two shops keep their product IDs in separate BSTs, and a combined catalogue needs all IDs from both trees in sorted order. Each BST's inorder traversal is already sorted, so the task is merging two sorted streams. Materialising both inorder lists and merging works with O(n + m) extra memory. The elegant version runs two iterative inorder traversals in lockstep, each with its own stack, and always advances the one whose next value is smaller. That needs only O(h₁ + h₂) extra memory.

Example: [2, 1, 4] and [1, 0, 3] → [0, 1, 1, 2, 3, 4].

Function signature

vector<int> getAllElements(TreeNode* root1, TreeNode* root2);

Test cases

Input (tree1, tree2)	Output	Explanation
([2, 1, 4], [1, 0, 3])	[0, 1, 1, 2, 3, 4]
([1, null, 8], [8, 1])	[1, 1, 8, 8]	Duplicates across trees are kept
([], [5, 1, 7])	[1, 5, 7]
([3], [])	[3]
([], [])	[]

(Confirm: each tree is a valid BST; values may repeat across the two trees.)

How interviewers phrase it

• "Given two binary search trees, return a list containing all the integers from both trees sorted in ascending order" (LeetCode 1305; GeeksforGeeks "Merge two BSTs").

Clarifying questions to ask

1. Keep duplicates? (Yes.)
2. Is extra memory limited? (That decides between merging arrays and merging with stacks.)
3. Do I return a list or build a new BST? (A list here.)

Follow-ups to expect

1. "Simplest approach?"
2. "How do the two stacks work?"
3. "Why is it still linear?"
4. "How would you build a balanced BST from the merged list?"
5. "Complexity?"

Related questions

• Correct BST with two nodes swapped Hard
• Kth Smallest and Largest element in BST Medium
• Construct a BST from a preorder traversal Medium
• Implement Min Stack Hard
• Trapping Rainwater Hard
• Largest rectangle in a histogram Hard

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in