All Elements in Two Binary Search Trees

All Elements in Two Binary Search Trees

What is this problem about?

The "All Elements in Two Binary Search Trees interview question" asks you to take two separate Binary Search Trees (BSTs) and combine all their values into a single, sorted list. A BST is a tree where for any given node, the left child has a smaller value and the right child has a larger value. This property is the key to solving this problem efficiently without needing a heavy-duty sorting algorithm at the end.

Why is this asked in interviews?

Meta and Amazon interviewers use the "All Elements in Two Binary Search Trees coding problem" to test a candidate's knowledge of tree traversals and linear merging. It evaluates if you understand that an "in-order" traversal of a BST yields values in sorted order. Furthermore, it tests your ability to merge two sorted lists, which is a fundamental concept in algorithms like Merge Sort.

Algorithmic pattern used

This problem combines the Binary Tree In-order Traversal and the Two Pointers (Merge) patterns.

1. Traverse: Perform an in-order traversal on both trees independently to get two sorted lists.
2. Merge: Use two pointers to iterate through both lists simultaneously, always picking the smaller element to build the final result. This approach ensures an $O(M + N)$ time complexity, where $M$ and $N$ are the number of nodes in each tree.

Example explanation

Suppose Tree 1 has values {2, 1, 4} and Tree 2 has values {1, 0, 3}.

1. In-order traversal of Tree 1: [1, 2, 4]
2. In-order traversal of Tree 2: [0, 1, 3]
3. Merge Step:
   • Compare 1 and 0 -> Pick 0. Result: [0]
   • Compare 1 and 1 -> Pick 1. Result: [0, 1]
   • Compare 2 and 1 -> Pick 1. Result: [0, 1, 1]
   • Compare 2 and 3 -> Pick 2. Result: [0, 1, 1, 2]
   • Compare 4 and 3 -> Pick 3. Result: [0, 1, 1, 2, 3]
   • Remaining 4 -> Result: [0, 1, 1, 2, 3, 4]

Common mistakes candidates make

• Generic Sorting: Using a traversal like BFS or DFS to collect all elements into one list and then calling sort(). This is $O(N \log N)$, whereas the merge approach is $O(N)$.
• Space Complexity: Forgetting that storing the lists takes $O(N)$ space.
• Recursive Stack Overflow: For very deep trees, a recursive in-order traversal might hit stack limits; using an iterative approach with a stack is often safer.

Interview preparation tip

Always remember the property: In-order = Sorted for BSTs. This is a recurring theme in tree problems. Practice merging two sorted arrays using two pointers, as this skill is universally applicable across many coding challenges.