← OYO questions

Merge two BSTs with limited extra space

Filed under OYO · Also reported at Sprinklr

Free read 2 of 3

Maintain 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

  1. Maintain two stacks to perform lazy in-order traversals on both BSTs concurrently.

Solution

O(N1 + N2) time, O(H1 + H2) space

Python
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.