# Merging Binary Trees

Program for merging two binary trees

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

class Node {
public:
int data;
Node * left;
Node * right;
Node(int x, Node * left_node = nullptr, Node * right_node = nullptr) :
data(x), left(left_node), right(right_node)
{}
};

// The binary trees are merged together with the root being root1
Node* MergeTrees (Node* root1, Node* root2) {

if (root1 == nullptr && root2 == nullptr)
return nullptr;

if (root1 == nullptr)
return root2;

if (root2 == nullptr)
return root1;

root1->data = (root1->data + root2->data);
root1->left = MergeTrees(root1->left, root2->left);
root1->right = MergeTrees(root1->right, root2->right);

return root1;
}

void PreOrder (Node * root) {
if (root != nullptr) {
cout << root->data << " ";
PreOrder(root->left);
PreOrder(root->right);
}
}

int main () {

/* Binary tree A
9
/   \
5     16
\      \
7       18
/ \
6   8
*/
Node node6(6), node8(8);
Node node7(7, &node6, &node8);
Node node18(18);
Node node16(16, nullptr, &node18);
Node node5(5, nullptr, &node7);
Node root_A(9, &node5, &node16);

/* Binary Tree B
18
\
25
/
20   */

Node _node20(20);
Node _node25(25, &_node20, nullptr);
Node root_B(18, nullptr, &_node25);

root_A = *MergeTrees(&root_A, &root_B);

/* Merged binary tree ( A + B )
27
/   \
5     41
\   /  \
7  20   18
/ \
6   8
*/
cout << "Nodes of merged tree printed in preorder : ";
PreOrder(&root_A);  // 27 5 7 6 8 41 20 18

return 0;
}
``````

Output

``````Nodes of merged tree printed in preorder : 27 5 7 6 8 41 20 18
``````