All Elements in Two Binary Search Trees — Problem & Solution
All Elements in Two Binary Search Trees solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
All Elements in Two Binary Search Trees is a medium coding problem on sorting, depth-first search and trees, asked in Amazon, Microsoft and Meta interviews.
- Difficulty: Medium
- Topics: Sorting, Depth-First Search, Trees
- Asked at: Amazon, Microsoft, Meta
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given the roots root1 and root2 of two binary search trees (in each, every value in a node's left subtree is smaller than the node's value and every value in its right subtree is larger).
Return one list holding every value from both trees, sorted in ascending order. A value present in both trees appears twice.
Example 1
Input: root1 = [2,1,4], root2 = [1,0,3]
Output: [0,1,1,2,3,4]
Explanation: The first tree holds 1, 2, 4 and the second 0, 1, 3; together, sorted: 0, 1, 1, 2, 3, 4.
Example 2
Input: root1 = [1,null,8], root2 = [8,1]
Output: [1,1,8,8]
Explanation: Values that appear in both trees appear twice in the answer.
Example 3
Input: root1 = [], root2 = [5,1,7]
Output: [1,5,7]
Explanation: The first tree is empty, so the answer is just the second tree in order.
Constraints
0 <= number of nodes in each tree <= 5000-10^5 <= Node.val <= 10^5each tree is a valid binary search tree
Hints for All Elements in Two Binary Search Trees
Hint 1
An in-order walk of a binary search tree lists its values already sorted.
Hint 2
So you have two sorted lists — you do not need a general sort.
Hint 3
Merge them the way merge sort does: repeatedly take the smaller front element, then append whatever is left.
How to solve All Elements in Two Binary Search Trees
In-order traversal turns each BST into a sorted list in linear time, and two sorted lists merge into one in linear time.
Approach
- Walk each tree in order (left, node, right), appending values to its own list.
- Keep an index into each list; while both have elements left, append the smaller front value and advance that index.
- Append the rest of whichever list is not exhausted.
Why it works
The BST property makes every value of the left subtree smaller than the node and every value of the right subtree larger, so in-order output is sorted. The merge always appends the smallest value not yet used, so its output is sorted and contains every value exactly once per occurrence.
Complexity
- Time —
O(n + m) - Space —
O(n + m) for the lists, plus O(h) recursion
Pitfalls
- Concatenating and sorting works but costs O((n + m) log(n + m)); the merge is linear.
- Either tree may be empty.
Reference solution
Python
from typing import List, Optional
def getAllElements(root1: Optional[TreeNode], root2: Optional[TreeNode]) -> List[int]:
def inorder(node, out):
if node is None:
return
inorder(node.left, out)
out.append(node.val)
inorder(node.right, out)
a, b = [], []
inorder(root1, a)
inorder(root2, b)
out = []
i = j = 0
while i < len(a) and j < len(b):
if a[i] <= b[j]:
out.append(a[i])
i += 1
else:
out.append(b[j])
j += 1
out.extend(a[i:])
out.extend(b[j:])
return outJava
public static int[] getAllElements(TreeNode root1, TreeNode root2) {
List<Integer> a = new ArrayList<>(), b = new ArrayList<>();
inorderInto(root1, a);
inorderInto(root2, b);
int[] out = new int[a.size() + b.size()];
int i = 0, j = 0, k = 0;
while (i < a.size() && j < b.size()) out[k++] = a.get(i) <= b.get(j) ? a.get(i++) : b.get(j++);
while (i < a.size()) out[k++] = a.get(i++);
while (j < b.size()) out[k++] = b.get(j++);
return out;
}
static void inorderInto(TreeNode node, List<Integer> out) {
if (node == null) return;
inorderInto(node.left, out);
out.add(node.val);
inorderInto(node.right, out);
}C++
void inorderInto(TreeNode* node, vector<int>& out);
vector<int> getAllElements(TreeNode* root1, TreeNode* root2) {
vector<int> a, b, out;
inorderInto(root1, a);
inorderInto(root2, b);
size_t i = 0, j = 0;
while (i < a.size() && j < b.size()) out.push_back(a[i] <= b[j] ? a[i++] : b[j++]);
while (i < a.size()) out.push_back(a[i++]);
while (j < b.size()) out.push_back(b[j++]);
return out;
}
void inorderInto(TreeNode* node, vector<int>& out) {
if (!node) return;
inorderInto(node->left, out);
out.push_back(node->val);
inorderInto(node->right, out);
}JavaScript
var getAllElements = function(root1, root2) {
var a = [], b = [], out = [];
inorderInto(root1, a);
inorderInto(root2, b);
var i = 0, j = 0;
while (i < a.length && j < b.length) out.push(a[i] <= b[j] ? a[i++] : b[j++]);
while (i < a.length) out.push(a[i++]);
while (j < b.length) out.push(b[j++]);
return out;
};
var inorderInto = function(node, out) {
if (node === null) return;
inorderInto(node.left, out);
out.push(node.val);
inorderInto(node.right, out);
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 274 sorting problems · the whole catalogue
Learn the technique: Sorting Algorithms · Depth-First Search (DFS)