class Solution
{
    public:
    //Function to return a list of integers denoting the node
    //values of both the BST in a sorted order.
    vector<int> v1, v2;
    void dfs(Node *root, int t) {
        if(!root) {
            return;
        }
        dfs(root->left, t);
        if(t == 1) {
            v1.push_back(root->data);
        }
        else {
            v2.push_back(root->data);
        }
        dfs(root->right, t);
    }
    vector<int> merge(Node *root1, Node *root2)
    {
        dfs(root1, 1);
        dfs(root2, 2);

        vector<int> v;
        int i = 0,  j = 0;
        while(i < (int) v1.size() and j < (int) v2.size()) {
            if(v1[i] < v2[j]) {
                v.push_back(v1[i]);
                i++;
            }
            else if(v1[i] > v2[j]) {
                v.push_back(v2[j]);
                j++;
            }
            else {
                v.push_back(v1[i]);
                v.push_back(v1[i]);
                i++;
                j++;
            }
        }
        while(i < (int) v1.size()) {
            v.push_back(v1[i]);
            i++;
        }
        while(j < (int) v2.size()) {
            v.push_back(v2[j]);
            j++;
        }
        return v;
    }
};