All Elements in Two Binary Search Trees

Problem Description

Given two binary search trees root1 and root2, return a list containing all the integers from both trees sorted in ascending order.

Key Insights

• Both trees are binary search trees (BST), meaning that for each node, all elements in the left subtree are smaller and all elements in the right subtree are larger.
• An in-order traversal of a BST yields elements in sorted order.
• By performing an in-order traversal on both trees, we can retrieve all elements in sorted order and then merge the two sorted lists.

Space and Time Complexity

Time Complexity: O(n + m), where n and m are the number of nodes in root1 and root2, respectively. This accounts for the time taken to traverse both trees and merge the results. Space Complexity: O(n + m) for storing the elements from both trees in separate lists before merging.

Solution

To solve this problem, we can utilize in-order traversal to extract elements from both binary search trees in sorted order. We will then merge the two sorted lists to obtain the final result. The process involves:

1. Performing in-order traversal on each tree to get two sorted lists.
2. Merging the two sorted lists into one sorted list.

Code Solutions