Merge Two Binary Trees by doing Node Sum (Recursive and Iterative)
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.
Example:
Input: Tree 1 Tree 2 2 3 / \ / \ 1 4 6 1 / \ \ 5 2 7 Output: Merged tree: 5 / \ 7 5 / \ \ 5 2 7
Note: The merging process must start from the root nodes of both trees.
Recursive Algorithm:
- Traverse the tree in Pre-order fashion
- Check if both the tree nodes are NULL
- If not, then update the value
- Recur for left subtrees
- Recur for right subtrees
- Return root of updated Tree
C++
// 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 */ cout<<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); /* Let us construct the second Binary Tree 4 / \ 1 7 / / \ 3 2 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; } // This code is contributed by Aditya Kumar (adityakumar129) |
C
// C program to Merge Two Binary Trees #include<stdio.h> #include<stdlib.h> /* A binary tree node has data, pointer to left child and a pointer to right child */ typedef struct Node { int data; struct Node *left, *right; }Node; /* Helper function that allocates a new node with the given data and NULL left and right pointers. */ Node *newNode( int data) { Node *new_node = (Node *) malloc ( sizeof (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); /* Let us construct the second Binary Tree 4 / \ 1 7 / / \ 3 2 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; } // This code is contributed by Aditya Kumar (adityakumar129) |
Java
// Java program to Merge Two Binary Trees /* A binary tree node has data, pointer to left child and a pointer to right child */ class Node { int data; Node left, right; public Node( int data, Node left, Node right) { this .data = data; this .left = left; this .right = right; } /* Helper method that allocates a new node with the given data and NULL left and right pointers. */ static Node newNode( int data) { return new Node(data, null , null ); } /* Given a binary tree, print its nodes in inorder*/ static void inorder(Node node) { if (node == null ) return ; /* first recur on left child */ inorder(node.left); /* then print the data of node */ System.out.printf( "%d " , node.data); /* now recur on right child */ inorder(node.right); } /* Method to merge given two binary trees*/ static Node MergeTrees(Node t1, Node t2) { if (t1 == null ) return t2; if (t2 == null ) return t1; t1.data += t2.data; t1.left = MergeTrees(t1.left, t2.left); t1.right = MergeTrees(t1.right, t2.right); return t1; } // Driver method public static void main(String[] args) { /* 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 ); /* Let us construct the second Binary Tree 4 / \ 1 7 / / \ 3 2 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); System.out.printf( "The Merged Binary Tree is:\n" ); inorder(root3); } } // This code is contributed by Gaurav Miglani |
Python3
# Python3 program to Merge Two Binary Trees # Helper class that allocates a new node # with the given data and None left and # right pointers. class newNode: def __init__( self , data): self .data = data self .left = self .right = None # Given a binary tree, prints nodes # in inorder def inorder(node): if ( not node): return # first recur on left child inorder(node.left) # then print the data of node print (node.data, end = " " ) # now recur on right child inorder(node.right) # Function to merge given two # binary trees def MergeTrees(t1, t2): if ( not t1): return t2 if ( not 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 if __name__ = = '__main__' : # Let us construct the first Binary Tree # 1 # / \ # 2 3 # / \ \ # 4 5 6 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 ) # Let us construct the second Binary Tree # 4 # / \ # 1 7 # / / \ # 3 2 6 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 ) root3 = MergeTrees(root1, root2) print ( "The Merged Binary Tree is:" ) inorder(root3) # This code is contributed by PranchalK |
C#
// C# program to Merge Two Binary Trees using System; /* A binary tree node has data, pointer to left child and a pointer to right child */ public class Node { public int data; public Node left, right; public Node( int data, Node left, Node right) { this .data = data; this .left = left; this .right = right; } /* Helper method that allocates a new node with the given data and NULL left and right pointers. */ public static Node newNode( int data) { return new Node(data, null , null ); } /* Given a binary tree, print its nodes in inorder*/ public static void preorder(Node node) { if (node == null ) { return ; } /* then print the data of node */ Console.Write( "{0:D} " , node.data); /* first recur on left child */ inorder(node.left); /* now recur on right child */ inorder(node.right); } /* Method to merge given two binary trees*/ public static Node MergeTrees(Node t1, Node t2) { if (t1 == null ) { return t2; } if (t2 == null ) { return t1; } t1.data += t2.data; t1.left = MergeTrees(t1.left, t2.left); t1.right = MergeTrees(t1.right, t2.right); return t1; } // Driver Code public static void Main( string [] args) { /* 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); /* Let us construct the second Binary Tree 4 / \ 1 7 / / \ 3 2 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); Console.Write( "The Merged Binary Tree is:\n" ); preorder(root3); } } // This code is contributed by Shrikant13 |
Javascript
<script> // Javascript program to Merge Two Binary Trees class Node { constructor(data) { this .left = null ; this .right = null ; this .data = data; } } // Helper method that allocates a new // node with the given data and NULL // left and right pointers. function newNode(data) { return new Node(data); } // Given a binary tree, print its // nodes in inorder function inorder(node) { if (node == null ) return ; // First recur on left child inorder(node.left); // Then print the data of node document.write(node.data + " " ); // Now recur on right child inorder(node.right); } // Method to merge given two binary trees function MergeTrees(t1, t2) { if (t1 == null ) return t2; if (t2 == null ) return t1; t1.data += t2.data; t1.left = MergeTrees(t1.left, t2.left); t1.right = MergeTrees(t1.right, t2.right); return t1; } // Driver code /* Let us construct the first Binary Tree 1 / \ 2 3 / \ \ 4 5 6 */ let 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); /* Let us construct the second Binary Tree 4 / \ 1 7 / / \ 3 2 6 */ let 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); let root3 = MergeTrees(root1, root2); document.write( "The Merged Binary Tree is:" + "</br>" ); inorder(root3); // This code is contributed by divyeshrabadiya07 </script> |
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).
Iterative Algorithm:
- Create a stack
- Push the root nodes of both the trees onto the stack.
- While the stack is not empty, perform following steps :
- Pop a node pair from the top of the stack
- For every node pair removed, add the values corresponding to the two nodes and update the value of the corresponding node in the first tree
- If the left child of the first tree exists, push the left child(pair) of both the trees onto the stack.
- If the left child of the first tree doesn’t exist, append the left child of the second tree to the current node of the first tree
- Do same for right child pair as well.
- If both the current nodes are NULL, continue with popping the next nodes from the stack.
- Return root of updated Tree
Implementation:
C++
// 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; }; // Structure to store node pair onto stack struct snode { Node *l, *r; }; /* 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; stack<snode> s; snode temp; temp.l = t1; temp.r = t2; s.push(temp); snode n; while (! s.empty()) { n = s.top(); s.pop(); if (n.l == NULL|| n.r == NULL) continue ; n.l->data += n.r->data; if (n.l->left == NULL) n.l->left = n.r->left; else { snode t; t.l = n.l->left; t.r = n.r->left; s.push(t); } if (n.l->right == NULL) n.l->right = n.r->right; else { snode t; t.l = n.l->right; t.r = n.r->right; s.push(t); } } 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); /* Let us construct the second Binary Tree 4 / \ 1 7 / / \ 3 2 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; } |
Java
// Java program to Merge Two Binary Trees import java.util.*; class GFG{ /* A binary tree node has data, pointer to left child and a pointer to right child */ static class Node { int data; Node left, right; }; // Structure to store node pair onto stack static class snode { Node l, r; }; /* Helper function that allocates a new node with the given data and null left and right pointers. */ static 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*/ static void inorder(Node node) { if (node == null ) return ; /* first recur on left child */ inorder(node.left); /* then print the data of node */ System.out.printf( "%d " , node.data); /* now recur on right child */ inorder(node.right); } /* Function to merge given two binary trees*/ static Node MergeTrees(Node t1, Node t2) { if ( t1 == null ) return t2; if ( t2 == null ) return t1; Stack<snode> s = new Stack<>(); snode temp = new snode(); temp.l = t1; temp.r = t2; s.add(temp); snode n; while (! s.isEmpty()) { n = s.peek(); s.pop(); if (n.l == null || n.r == null ) continue ; n.l.data += n.r.data; if (n.l.left == null ) n.l.left = n.r.left; else { snode t = new snode(); t.l = n.l.left; t.r = n.r.left; s.add(t); } if (n.l.right == null ) n.l.right = n.r.right; else { snode t = new snode(); t.l = n.l.right; t.r = n.r.right; s.add(t); } } return t1; } // Driver code public static void main(String[] args) { /* 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 ); /* Let us construct the second Binary Tree 4 / \ 1 7 / / \ 3 2 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); System.out.printf( "The Merged Binary Tree is:\n" ); inorder(root3); } } // This code is contributed by gauravrajput1 |
Python3
# Python3 program to Merge Two Binary Trees ''' A binary tree node has data, pointer to left child and a pointer to right child ''' class Node: def __init__( self , data): self .data = data self .left = None self .right = None # Structure to store node pair onto stack class snode: def __init__( self , l, r): self .l = l self .r = r ''' Helper function that allocates a new node with the given data and None left and right pointers. ''' def newNode(data): new_node = Node(data) return new_node ''' Given a binary tree, print its nodes in inorder''' def inorder(node): if ( not node): return ; ''' first recur on left child ''' inorder(node.left); ''' then print the data of node ''' print (node.data, end = ' ' ); ''' now recur on right child ''' inorder(node.right); ''' Function to merge given two binary trees''' def MergeTrees(t1, t2): if ( not t1): return t2; if ( not t2): return t1; s = [] temp = snode(t1, t2) s.append(temp); n = None while ( len (s) ! = 0 ): n = s[ - 1 ] s.pop(); if (n.l = = None or n.r = = None ): continue ; n.l.data + = n.r.data; if (n.l.left = = None ): n.l.left = n.r.left; else : t = snode(n.l.left, n.r.left) s.append(t); if (n.l.right = = None ): n.l.right = n.r.right; else : t = snode(n.l.right, n.r.right) s.append(t); return t1; # Driver code if __name__ = = '__main__' : ''' Let us construct the first Binary Tree 1 / \ 2 3 / \ \ 4 5 6 ''' 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 ); ''' Let us construct the second Binary Tree 4 / \ 1 7 / / \ 3 2 6 ''' 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 ); root3 = MergeTrees(root1, root2); print ( "The Merged Binary Tree is:" ); inorder(root3); # This code is contributed by rutvik76 |
C#
// C# program to Merge Two Binary Trees using System; using System.Collections.Generic; class GFG{ // A binary tree node has data, pointer // to left child and a pointer to right // child public class Node { public int data; public Node left, right; }; // Structure to store node pair onto stack public class snode { public Node l, r; }; // Helper function that allocates a new // node with the given data and null // left and right pointers. static 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 static void inorder(Node node) { if (node == null ) return ; // First recur on left child inorder(node.left); // Then print the data of node Console.Write(node.data + " " ); // Now recur on right child inorder(node.right); } // Function to merge given two binary trees static Node MergeTrees(Node t1, Node t2) { if ( t1 == null ) return t2; if ( t2 == null ) return t1; Stack<snode> s = new Stack<snode>(); snode temp = new snode(); temp.l = t1; temp.r = t2; s.Push(temp); snode n; while (s.Count != 0) { n = s.Peek(); s.Pop(); if (n.l == null || n.r == null ) continue ; n.l.data += n.r.data; if (n.l.left == null ) n.l.left = n.r.left; else { snode t = new snode(); t.l = n.l.left; t.r = n.r.left; s.Push(t); } if (n.l.right == null ) n.l.right = n.r.right; else { snode t = new snode(); t.l = n.l.right; t.r = n.r.right; s.Push(t); } } return t1; } // Driver code public static void Main(String[] args) { /* 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); /* Let us construct the second Binary Tree 4 / \ 1 7 / / \ 3 2 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); Console.Write( "The Merged Binary Tree is:\n" ); inorder(root3); } } // This code is contributed by aashish1995 |
Javascript
<script> // JavaScript program to Merge Two Binary Trees /* A binary tree node has data, pointer to left child and a pointer to right child */ class Node { constructor() { this .data=0; this .left= this .right= null ; } } // Structure to store node pair onto stack class snode { constructor() { this .l= null ; this .r= null ; } } /* Helper function that allocates a new node with the given data and null left and right pointers. */ function newNode(data) { let 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*/ function inorder(node) { if (node == null ) return ; /* first recur on left child */ inorder(node.left); /* then print the data of node */ document.write(node.data+ " " ); /* now recur on right child */ inorder(node.right); } /* Function to merge given two binary trees*/ function MergeTrees(t1,t2) { if ( t1 == null ) return t2; if ( t2 == null ) return t1; let s = []; let temp = new snode(); temp.l = t1; temp.r = t2; s.push(temp); let n; while ( s.length!=0) { n = s.pop(); if (n.l == null || n.r == null ) continue ; n.l.data += n.r.data; if (n.l.left == null ) n.l.left = n.r.left; else { let t = new snode(); t.l = n.l.left; t.r = n.r.left; s.push(t); } if (n.l.right == null ) n.l.right = n.r.right; else { let t = new snode(); t.l = n.l.right; t.r = n.r.right; s.push(t); } } return t1; } // Driver code /* Let us construct the first Binary Tree 1 / \ 2 3 / \ \ 4 5 6 */ let 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); /* Let us construct second Binary Tree 4 / \ 1 7 / / \ 3 2 6 */ let 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); let root3 = MergeTrees(root1, root2); document.write( "The Merged Binary Tree is:<br>" ); inorder(root3); // This code is contributed by unknown2108 </script> |
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 stack can go upto n in case of a skewed tree.
Contact Us