 C++ program to merge Two binary search trees

#include<bits/stdc++.h>
using namespace std;
struct node
int data;
struct node* left;
struct node* right;
};

struct node* getNode(int data)
struct node* node = (struct node*)
malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;

return(node);
}
// function to merge two sorted arrays into one

int *merge(int arr1[], int arr2[], int m, int n)
// mergedArr[] is our resultant array
int *mergedArr = new int[m + n];
int i = 0, j = 0, k = 0;

while (i < m && j < n)
if (arr1[i] < arr2[j])
mergedArr[k] = arr1[i];
i++;
else
mergedArr[k] = arr2[j];
j++;
k++;

// If there are more elements in first array
while (i < m)
mergedArr[k] = arr1[i];
i++; k++;

// If there are more elements in second array
while (j < n)
mergedArr[k] = arr2[j];
j++; k++;

return mergedArr;

// A  function that stores inorder traversal of a tree in an array so that we get sorted array
void storeInorder(struct node* node, int inorder[], int &k)
if (node == NULL)
return;

storeInorder(node->left, inorder, k);

inorder[k++] = node->data;
// increase k for next entry

storeInorder(node->right, inorder, k);
}

/* A function that conververt to Binary Search Tree from a sorted array  */
struct node* sortedArrayToBST(int arr[], int start, int end)
/* Base Case */
if (start > end)
return NULL;

/* Get the middle element and make it root */
int mid = (start + end)/2;
struct node *root = getNode(arr[mid]);

/* Recursively construct the left subtree and make it
left child of root */
root->left = sortedArrayToBST(arr, start, mid-1);

/* Recursively construct the right subtree and make it
right child of root */
root->right = sortedArrayToBST(arr, mid+1, end);

return root;
}
/* This function merges two BSTs with roots as node1 and node2.
m and n are the sizes of the trees respectively */
struct node* mergeTrees(struct node *node1, struct node *node2, int m, int n)
// Store inorder traversal of first tree in an array arr1[]
int a[m] ;
int i=0;
storeInorder(node1, a,i);

// Store inorder traversal of second tree in another array arr2[]
int b[n];
int j = 0;
storeInorder(node2,b,j);

// Merge the two sorted array into one
int *mergeTheArray = merge(a,b, m, n);

// Construct a tree from the merged array and return root of the tree
return sortedArrayToBST (mergeTheArray, 0, m+n-1);

// A function to print inorder traversal of a constructed binary tree
void printInorder(struct node* node)
if (node == NULL)
return;

printInorder(node->left);

cout<<node->data<<" ";

printInorder(node->right);

int main()
/* Create following tree as first  BST
84
/ \
74  90
/ \
20  78
*/
struct node *root1 = getNode(84);
root1->left = getNode(74);
root1->right = getNode(90);
root1->left->left = getNode(20);
root1->left->right = getNode(78);

/* Create following tree as second  BST
95
/ \
30 100
/    \
25     105
*/
struct node *root2 = getNode(95);
root2->left = getNode(30);
root2->right = getNode(100);
root2->left->left = getNode(25);
root2->right->right = getNode(105);
struct node *mergedTree = mergeTrees(root1, root2, 5, 5);

printf ("The Inorder traversal of the merged tree \n");
printInorder(mergedTree);

return 0;
/* OUTPUT ::
20 25 30 74 78 84 90 95 100 105
*/ 