Merge two BST ‘s

Given two BSTs, return elements of both BSTs in sorted form.

• Time : O(n + m)
• Space : O(d)

c++

class Solution
{
public:
    //Function to return a list of integers denoting the node
    //values of both the BST in a sorted order.
    vector<int> merge(Node *root1, Node *root2)
    {
        vector<Node*> st1, st2;
        vector<int> res;
        while(root1) {
            st1.push_back(root1);
            root1 = root1->left;
        }
        while(root2) {
            st2.push_back(root2);
            root2 = root2->left;
        }
        while(!st1.empty() and !st2.empty()) {
            auto& mi = (st1.back()->data > st2.back()->data ? st2 : st1);
            auto node = mi.back();
            mi.pop_back();
            res.push_back(node->data);
            node = node->right;
            while(node) {
                mi.push_back(node);
                node = node->left;
            }
        }
        auto& st = (st1.empty() ? st2 : st1);
        while(!st.empty()) {
            auto node = st.back();
            st.pop_back();
            res.push_back(node->data);
            node = node->right;
            while(node) {
                st.push_back(node);
                node = node->left;
            }
        }

        return res;
    }
};