The idea behind merging binary trees is to combine two binary trees into a single binary tree according to a specific set of rules.
Rules
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
Complexity: The above method ensures that every node is processed exactly once, thus making the time complexity O(n) where ’n’ is the number of nodes in the larger tree.
© 2019-2026 Algotree.org | All rights reserved.
This content is provided for educational purposes. Feel free to learn, practice, and share knowledge.
For questions or contributions, visit algotree.org
"Talk is cheap. Show me the code. - Linus Torvalds"