Merge Two Binary Trees by doing Node Sum (Recursive and Iterative)

Software Development
#1

Hello Everyone,

Given two binary trees. We need to merge them into a new binary tree. The merge rule is that if two nodes overlap, then sum node values up as the new value of the merged node. Otherwise, the non-null node will be used as the node of new tree.

Recursive Algorithm:

  1. Traverse the tree in Preorder fashion
  2. Check if both the tree nodes are NULL
  3. If not, then update the value
  4. Recur for left subtrees
  5. Recur for right subtrees
  6. Return root of updated Tree

// C++ program to Merge Two Binary Trees

#include <bits/stdc++.h>

using namespace std;

/* A binary tree node has data, pointer to left child

and a pointer to right child */

struct Node

{

int data;

struct Node *left, *right;

};

/* Helper function that allocates a new node with the

given data and NULL left and right pointers. */

Node *newNode( int data)

{

Node *new_node = new Node;

new_node->data = data;

new_node->left = new_node->right = NULL;

return new_node;

}

/* Given a binary tree, print its nodes in inorder*/

void inorder(Node * node)

{

if (!node)

return ;

/* first recur on left child */

inorder(node->left);

/* then print the data of node */

printf ( "%d " , node->data);

/* now recur on right child */

inorder(node->right);

}

/* Function to merge given two binary trees*/

Node *MergeTrees(Node * t1, Node * t2)

{

if (!t1)

return t2;

if (!t2)

return t1;

t1->data += t2->data;

t1->left = MergeTrees(t1->left, t2->left);

t1->right = MergeTrees(t1->right, t2->right);

return t1;

}

// Driver code

int main()

{

/* Let us construct the first Binary Tree

1

/ \

2 3

/ \ \

4 5 6

*/

Node *root1 = newNode(1);

root1->left = newNode(2);

root1->right = newNode(3);

root1->left->left = newNode(4);

root1->left->right = newNode(5);

root1->right->right = newNode(6);

Node *root2 = newNode(4);

root2->left = newNode(1);

root2->right = newNode(7);

root2->left->left = newNode(3);

root2->right->left = newNode(2);

root2->right->right = newNode(6);

Node *root3 = MergeTrees(root1, root2);

printf ( "The Merged Binary Tree is:\n" );

inorder(root3);

return 0;

}

Output:

The Merged Binary Tree is: 7 3 5 5 2 10 12

Complexity Analysis:

  • Time complexity : O(n)
    A total of n nodes need to be traversed. Here, n represents the minimum number of nodes from the two given trees.

  • Auxiliary Space : O(n)
    The depth of the recursion tree can go upto n in case of a skewed tree. In average case, depth will be O(logn).