Merge two BSTs with limited extra space
Filed under OYO · Also reported at Sprinklr
Free read 2 of 3Maintain two stacks to perform lazy in-order traversals on both BSTs concurrently.
The question
Given the roots of two Binary Search Trees `root1` and `root2`, return a single sorted list containing all elements from both trees using limited extra space (proportional to the tree heights).
Constraints
- 0 <= number of nodes in each tree <= 5000
- -10^4 <= Node.val <= 10^4
Examples
- Input
- root1 = [2,1,4], root2 = [1,0,3]
- Output
- [0,1,1,2,3,4]
- Why
- Merging elements from both BSTs yields the sorted list [0,1,1,2,3,4].
Approach
Maintain two stacks to perform lazy in-order traversals on both BSTs concurrently.
For both trees, push left child nodes onto their respective stacks until reaching a leaf.
Compare top elements of both stacks. Pop the smaller value into the result list and advance its node pointer to its right child.
Continue until both stacks and active pointers are completely empty.
Solution
O(N1 + N2) time, O(H1 + H2) space
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def getAllElements(self, root1: TreeNode, root2: TreeNode) -> list[int]:
s1, s2 = [], []
res = []
c1, c2 = root1, root2
while c1 or c2 or s1 or s2:
while c1:
s1.append(c1)
c1 = c1.left
while c2:
s2.append(c2)
c2 = c2.left
if not s2 or (s1 and s1[-1].val <= s2[-1].val):
node = s1.pop()
res.append(node.val)
c1 = node.right
else:
node = s2.pop()
res.append(node.val)
c2 = node.right
return res
Tips
- What they are testing: Tests advanced BST properties, controlled iterative in-order traversal, and two-pointer merging.
- Common mistake: Dumping all elements of both trees into full arrays first, violating the space optimization goal of O(H1 + H2).
Related OYO questions
Collected from public candidate posts and coding forums. Updated Nov 2026.