Two branches of a library each keep their book IDs in a binary search tree with distinct values (an ID may appear in both trees). Return one ascending list with every ID from both trees; an ID present in both appears twice.
Examples
4 5
/ \ / \
2 6 1 8
Input: root1 = build_tree([4, 2, 6]), root2 = build_tree([5, 1, 8])
Output: [1, 2, 4, 5, 6, 8]
3
/ 3
1
Input: root1 = build_tree([3, 1]), root2 = build_tree([3])
Output: [1, 3, 3]
Constraints
0 <= nodes in each tree <= 3000- Values within one tree are distinct integers
- O(n + m) time
Goals
- Read each tree in sorted order
- Merge two sorted sequences in linear time