Getting undesired result while merging two BST

Question

The problem is to merge two binary tree, i tried my approach it is giving correct answer in dry run but when I coded it's just printing BST of tree1 and tree2 it's not merging the value...

/*
TODO: MERGE TWO BST
*/



#include <iostream>
#include <vector>
using namespace std;

class BST
{
public:
    int data;
    BST *left;
    BST *right;
    BST(int data)
    {
        this->data = data;
        left = right = NULL;
    }
};

BST *insert(BST *root, int data)
{
    if (root == NULL)
    {
        root = new BST(data);
        return root;
    }
    if (data > root->data)
    {
        root->right = insert(root->right, data);
    }
    else
    {
        root->left = insert(root->left, data);
    }
    return root;
}

// step1:method to  store inorder traversal of tree to array
void inorder(BST *root, vector<int> &v)
{
    if (root == NULL)
    {
        return;
    }
    inorder(root->left, v);
    v.push_back(root->data);
    inorder(root->right, v);
}

vector<int> mergeArray(vector<int> &vec1, vector<int> &vec2)
{
    int i = 0;
    int j = 0;
    int k = 0;
    // an array to store merged of both and it's size is equal to sum to arr1 and arr2
    vector<int> ans(vec1.size() + vec2.size());
    // loop to array untile all the element is traverse in both
    while (i < vec1.size() && j < vec2.size())
    {
        if (vec1[i] < vec2[j])
        {
            ans[k++] = vec1[i];
            // ans.push_back(vec1[i]);
            i++;
        }
        else
        {
            ans[k++] = vec2[j];
            // ans.push_back(vec2[j]);
            j++;
        }
        // if any of the element has lower size then traverse another until it is fully traversed
        while (i < vec1.size())
        {
            ans[k++] = vec1[i];
            i++;
        }
        while (j < vec2.size())
        {
            ans[k++] = vec2[j];
            j++;
        }
    }
    return ans;
}
// step 3: method to create BST
BST *inorderToBST(int start, int end, vector<int> &v)
{
    if (start > end)
    {
        return NULL;
    }

    int mid = (start + end) / 2;
    BST *root = new BST(v[mid]);

    root->left = inorderToBST(start, mid - 1, v);
    root->right = inorderToBST(mid + 1, end, v);
    return root;
}

// TODO: master method
BST *mergeTwoBST(BST *root1, BST *root2)
{
    vector<int> tree1, tree2;
    // step: store inorder of both tree
    inorder(root1, tree1);
    inorder(root2, tree2);
    // merge both vector
    vector<int> mergedArray = mergeArray(tree1, tree2);
    int start = 0;
    int end = mergedArray.size();
    return inorderToBST(start, end, mergedArray);
}

void printInorder(BST *root)
{
    if (!root)
    {
        return;
    }
    printInorder(root->left);
    cout << root->data << " ";
    printInorder(root->right);
}

int main()
{
    BST *root1 = NULL;
    root1 = insert(root1, 100);
    insert(root1, 50);
    insert(root1, 300);
    insert(root1, 20);
    insert(root1, 70);

    BST *root2 = NULL;
    root2 = insert(root2, 80);
    insert(root2, 40);
    insert(root2, 120);
    // merge
    // cout << "Inorder of Tree 1: ";
    // printInorder(root1);
    // cout << endl
    //      << "Inorder of Tree 2: ";
    // printInorder(root2);
    BST *mergedTree = mergeTwoBST(root1, root2);
    cout << endl
         << "Inorder of merged Array : " << endl;
    printInorder(mergedTree);
    return 0;
}

The problem is to merge two binary tree, i tried my approach it is giving correct answer in dry run but when I coded it's just printing BST of tree1 and tree2 it's not merging the value...

Please suggest me the correction...

Answer 1

The body of the merging loop,

if (vec1[i] < vec2[j])
{
    ans[k++] = vec1[i];
    // ans.push_back(vec1[i]);
    i++;
}
else
{
    ans[k++] = vec2[j];
    // ans.push_back(vec2[j]);
    j++;
}
// if any of the element has lower size then traverse another until it is fully traversed
while (i < vec1.size())
{
    ans[k++] = vec1[i];
    i++;
}
while (j < vec2.size())
{
    ans[k++] = vec2[j];
    j++;
}

puts the smallest value in ans[0], then it copies all of vec1 into ans, then it copies all of vec2 into ans.
Then the loop ends, because you have reached the end of both vectors in the first iteration.

You need to finish the "neither vector has reached the end" loop before the other loops.

// Merge until we reach the end of at least one of the vectors.
while (i < vec1.size() && j < vec2.size())
{
    if (vec1[i] < vec2[j])
    {
        ans[k++] = vec1[i];
        i++;
    }
    else
    {
        ans[k++] = vec2[j];
        j++;
    }
}
// If there is anything left in one of the vectors, copy it.  
// Note that we know that at most one of the loop conditions can be true.
while (i < vec1.size())
{
    ans[k++] = vec1[i];
    i++;
}
while (j < vec2.size())
{
    ans[k++] = vec2[j];
    j++;
}