
class Solution {

    public List getAllElements(TreeNode root1, TreeNode root2) {
        List list1 = new ArrayList<>();
        inorder(root1, list1);

        List list2 = new ArrayList<>();
        inorder(root2, list2);

        int i = 0;
        int j = 0;

        List ans = new ArrayList<>();
        while (ans.size() != (list1.size() + list2.size())) {
            double val1 = Double.POSITIVE_INFINITY;
            if (i < list1.size()) {
                val1 = list1.get(i);
            }

            double val2 = Double.POSITIVE_INFINITY;
            if (j < list2.size()) {
                val2 = list2.get(j);
            }

            if (val1 < val2) {
                ans.add((int) val1);
                i++;
            } else {
                ans.add((int) val2);
                j++;
            }
        }
        return ans;
    }

    private void inorder(TreeNode node, List list) {
        if (node == null) {
            return;
        }

        inorder(node.left, list);
        list.add(node.val);
        inorder(node.right, list);
    }
}

Time Complexity: O(n) and Space Complexity: O(n)

The "All Elements in Two Binary Search Trees" problem requires finding all elements from two Binary Search Trees (BSTs) and returning them in a sorted list. Since both trees are Binary Search Trees, the values in each tree are sorted by definition. The goal is to merge the elements of the two BSTs and output them as a single sorted array.

Problem Statement

The roots of two binary search trees, root1 and root2, return a list containing all the elements from both trees, sorted in ascending order.

The tree node structure is given above. The task is to merge the values from the two binary search trees and return them in sorted order.

Approach

To solve this problem, we can take advantage of the fact that both trees are binary search trees (BSTs), where in-order traversal produces sorted values. The idea is to perform in-order traversal on both trees, retrieve their values, and then merge the two sorted lists.

Perform in-order traversal on both trees to get two sorted lists.
Merge the two sorted lists into one sorted list using a standard merging technique.
Return the merged list as the result.

Algorithm

The algorithm follows these steps:

Perform an in-order traversal on the first BST to collect its values in a sorted list.
Perform an in-order traversal on the second BST to collect its values in a sorted list.
Merge the two sorted lists into a single sorted list using the two-pointer technique.
Return the merged sorted list.

This approach ensures that we efficiently gather and merge the elements from both BSTs.

Example

Consider the following two binary search trees:

In this example, the values from both trees, when merged, should be: - Tree 1: [1, 2, 3, 4] - Tree 2: [1, 2, 3, 4] - Merged List: [1, 1, 2, 2, 3, 3, 4, 4]

Therefore, the solution should return the merged sorted list: - [1, 1, 2, 2, 3, 3, 4, 4]

Code Implementation

Below is the Python implementation of the algorithm to merge all elements from two binary search trees:

In this code: - The `getInOrder` function performs an in-order traversal of a given tree and returns the values as a sorted list. - The `getAllElements` function calls `getInOrder` on both trees to obtain their sorted lists and then merges them using two pointers. - The merged list is returned as the result, containing all elements from both trees in sorted order.

Time Complexity

The time complexity of this algorithm is O(m + n), where m and n are the number of nodes in the first and second trees, respectively. This is because we perform an in-order traversal of both trees (O(m + n)) and merge the two sorted lists (also O(m + n)).

The space complexity is O(m + n), where m and n are the sizes of the two trees. This space is used to store the sorted lists generated from the in-order traversal of both trees.

Conclusion

The "All Elements in Two Binary Search Trees" problem is an excellent exercise in utilizing in-order traversal to take advantage of the sorted property of binary search trees. By performing in-order traversals on both trees and merging the two sorted lists, we efficiently solve the problem in linear time.