Algotree > Algorithms > Tree & Graph Traversal > Merging Binary Trees

Merging Binary Trees

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

If both the trees have a node at the same position, merge the two nodes. The value of the merged node is the sum of the two merged nodes.
If just one of the trees has a node at a given position, use that node’s value in the merged tree.
If neither tree has a node at a given position, the merged tree should have a null at that position.

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.