Untitled

import java.util.*;

class TreeNode {
    int val;
    TreeNode left, right;

    TreeNode(int value) {
        val = value;
        left = right = null;
    }
}

public class MergeBSTs {
    public List<Integer> getAllElements(TreeNode root1, TreeNode root2) {
        // Step 1: Get sorted lists from in-order traversal
        List<Integer> list1 = new ArrayList<>();
        List<Integer> list2 = new ArrayList<>();
        inOrderTraversal(root1, list1);
        inOrderTraversal(root2, list2);

        // Step 2: Merge the two sorted lists
        return mergeSortedLists(list1, list2);
    }

    // Helper method for in-order traversal
    private void inOrderTraversal(TreeNode root, List<Integer> list) {
        if (root == null) return;

        inOrderTraversal(root.left, list);
        list.add(root.val);
        inOrderTraversal(root.right, list);
    }

    // Helper method to merge two sorted lists
    private List<Integer> mergeSortedLists(List<Integer> list1, List<Integer> list2) {
        List<Integer> mergedList = new ArrayList<>();
        int i = 0, j = 0;

        while (i < list1.size() && j < list2.size()) {
            if (list1.get(i) <= list2.get(j)) {
                mergedList.add(list1.get(i++));
            } else {
                mergedList.add(list2.get(j++));
            }
        }

        // Add remaining elements from list1 or list2
        while (i < list1.size()) mergedList.add(list1.get(i++));
        while (j < list2.size()) mergedList.add(list2.get(j++));

        return mergedList;
    }

    public static void main(String[] args) {
        // Example 1
        TreeNode root1 = new TreeNode(2);
        root1.left = new TreeNode(1);
        root1.right = new TreeNode(4);

        TreeNode root2 = new TreeNode(1);
        root2.left = new TreeNode(0);
        root2.right = new TreeNode(3);

        MergeBSTs solution = new MergeBSTs();
        System.out.println(solution.getAllElements(root1, root2));  // Output: [0, 1, 1, 2, 3, 4]

        // Example 2
        TreeNode root3 = new TreeNode(1);
        root3.right = new TreeNode(8);

        TreeNode root4 = new TreeNode(8);
        root4.left = new TreeNode(1);

        System.out.println(solution.getAllElements(root3, root4));  // Output: [1, 1, 8, 8]
    }
}