Merge BSTs In-Place | Dataford Interview Questions

Merge two binary search trees into one without using any extra space.

Asked in the technical stage. Implement merge_bsts(root1, root2). Each tree is represented by nested mutable dictionaries with keys val, left, and right, or by None. Return a list containing all values in the merged BST's inorder order. The algorithm must use O(1) auxiliary space, excluding the returned list, and may reuse and modify the input nodes.

Constraints

Each input is a valid BST represented by nested mutable dictionaries or None.
Each node has keys val, left, and right.
Duplicate values are allowed.
The combined number of nodes is at most 1000.
The returned list does not count as auxiliary space.
Do not use recursion, stacks, queues, or replacement tree nodes.

Function Signature

def merge_bsts(root1, root2):

Your question is Merge BSTs In-Place. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem

Merge two binary search trees into one without using any extra space.

Constraints

Each input is a valid BST represented by nested mutable dictionaries or None.
Each node has keys val, left, and right.
Duplicate values are allowed.
The combined number of nodes is at most 1000.
The returned list does not count as auxiliary space.
Do not use recursion, stacks, queues, or replacement tree nodes.

Function Signature

def merge_bsts(root1, root2):

Your question is Merge BSTs In-Place. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.