C++ program to merge Two binary search trees














































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
*/


Comments