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...

OT: The macro `NULL` is for backward compatibility with C. In C++ you should use `nullptr`. — Some programmer dude, May 05 '23 at 19:52
Regarding your problem, have you tried creating the merged vector using simple iterators? Like `std::vector ans(vec1.begin(), vec1.end()); ans.insert(ans.end(), vec2.begin(), vec2.end());`? If you want it sorted then just `std::sort(ans.begin(), ans.end());` after that? — Some programmer dude, May 05 '23 at 19:56
As for your current code, the two nested `while` loops in your `mergeArray` function should probably not be nested inside the main loop. You might want to do some [rubber duck debugging](https://en.wikipedia.org/wiki/Rubber_duck_debugging) of that function. Or some very real debugging using a [debugger](https://stackoverflow.com/questions/25385173/what-is-a-debugger-and-how-can-it-help-me-diagnose-problems). — Some programmer dude, May 05 '23 at 19:58

molbdnilo · Accepted Answer · 2023-05-06T08:49:50.143

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++;
}

Getting undesired result while merging two BST

1 Answers1