C++ Coding Exercise – How to Merge Two Binary Trees?

learn-to-code

Given two binary trees and imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the others are not. You 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 NOT null node will be used as the node of new tree.

Example 1:
Input: 
	Tree 1                     Tree 2                  
          1                         2                             
         / \                       / \                            
        3   2                     1   3                        
       /                           \   \                      
      5                             4   7                  
Output: 
Merged tree:
	     3
	    / \
	   4   5
	  / \   \ 
	 5   4   7

Note: The merging process must start from the root nodes of both trees.

C/C++ Binary Tree Definition

In C/C++, the binary tree data structure can be defined using structure, as follows where left or right trees are recursively defined.

1
2
3
4
5
6
7

 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

Recursion (Depth First Search)

Most tree-like problems can be solved via recursion because tree itself is a recursive data structure i.e. each left or right tree itself is also a tree.

This problem can be solved via DFS (Depth First Search) where we travel downwards as deep as possible before rewind to the trunk. If we don’t modify the original two trees, we can create a new tree and merge the process via DFS.

1
2
3
4
5
6
7
8
9
10
11
12

class Solution {
public:
    TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
        TreeNode* root;
        if (t1 == NULL) return t2;
        if (t2 == NULL) return t1;
        root = new TreeNode(t1->val + t2->val);
        root->left = mergeTrees(t1->left, t2->left);
        root->right = mergeTrees(t1->right, t2->right);
        return root;
    }
};

class Solution {
public:
    TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
        TreeNode* root;
        if (t1 == NULL) return t2;
        if (t2 == NULL) return t1;
        root = new TreeNode(t1->val + t2->val);
        root->left = mergeTrees(t1->left, t2->left);
        root->right = mergeTrees(t1->right, t2->right);
        return root;
    }
};

However, we can modify the original tree, in order to save memory space. For example, we can merge one tree to another.

1
2
3
4
5
6
7
8
9
10
11

class Solution {
public:
    TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
        if (t1 == nullptr) return t2;
        if (t2 == nullptr) return t1;
        t1->val += t2->val;
        t1->left = mergeTrees(t1->left, t2->left);
        t1->right = mergeTrees(t1->right, t2->right);
        return t1;
    }
};

class Solution {
public:
    TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
        if (t1 == nullptr) return t2;
        if (t2 == nullptr) return t1;
        t1->val += t2->val;
        t1->left = mergeTrees(t1->left, t2->left);
        t1->right = mergeTrees(t1->right, t2->right);
        return t1;
    }
};

Both recursion implementations have O(m) time complexity where m is the minimal number of nodes to travel from both tree. Both recursion has O(m) space complexity because the recursion uses stacks when the tree is skewed (e.g. linked list). However in reality, the average space complexity is O(logm) – the depth of the tree.

DFS implemented using stack

The DFS recursion can be implemented without recursion via manual stack.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

class Solution {
public:
    TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
        if (t1 == nullptr) return t2;
        if (t2 == nullptr) return t1;
        stack< pair<TreeNode*, TreeNode*> > st;
        st.push(make_pair(t1, t2));
        while (st.size() > 0) {
            auto cur = st.top();
            st.pop();
            if (cur.first == nullptr || cur.second == nullptr) {
                continue;
            }
            cur.first->val += cur.second->val; // sum the node values
            if (cur.first->left == nullptr) { // deal with left tree
                cur.first->left = cur.second->left;
            } else {
                st.push(make_pair(cur.first->left, cur.second->left));
            }
            if (cur.first->right == nullptr) { // deal with right tree
                cur.first->right = cur.second->right;
            } else {
                st.push(make_pair(cur.first->right, cur.second->right));
            }
        }       
        return t1;
    }
};

class Solution {
public:
    TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
        if (t1 == nullptr) return t2;
        if (t2 == nullptr) return t1;
        stack< pair<TreeNode*, TreeNode*> > st;
        st.push(make_pair(t1, t2));
        while (st.size() > 0) {
            auto cur = st.top();
            st.pop();
            if (cur.first == nullptr || cur.second == nullptr) {
                continue;
            }
            cur.first->val += cur.second->val; // sum the node values
            if (cur.first->left == nullptr) { // deal with left tree
                cur.first->left = cur.second->left;
            } else {
                st.push(make_pair(cur.first->left, cur.second->left));
            }
            if (cur.first->right == nullptr) { // deal with right tree
                cur.first->right = cur.second->right;
            } else {
                st.push(make_pair(cur.first->right, cur.second->right));
            }
        }       
        return t1;
    }
};

This iteration method has the same complexity as the DFS recursions – O(m) space and time complexity.

You may also like: C++ 编程练习题：如何合并两个二叉树？

–EOF (The Ultimate Computing & Technology Blog) —