Merge Two Binary Trees

Given two binary trees, merge them by laying one over the other. Where both trees have a node, the merged node's value is the sum of the two. Where only one tree has a node, that node is used as it is.

LeetCode: 617. Merge Two Binary Trees

Example

Text

    Tree 1         Tree 2           Merged
      1              2                3
     / \            / \              / \
    3   2          1   3            4   5
   /                \   \          / \   \
  5                  4   7        5   4   7

The examples print trees as value(left, right), with _ for a missing child.

Brute force: build a new tree

Recurse over both trees at once and allocate a new node for every position that exists in either tree. Where only one tree has a subtree, it is copied node by node.

A tree node is an object with an int val and two reference fields, left and right. A missing child is null, and the empty tree is a null root. The fields are mutable, so no wrapper type is needed.

Java

public class Main {
    static class TreeNode {
        int val;
        TreeNode left, right;
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    static TreeNode node(int val, TreeNode left, TreeNode right) {
        return new TreeNode(val, left, right);
    }

    static TreeNode leaf(int val) {
        return new TreeNode(val, null, null);
    }

    static TreeNode copy(TreeNode t) {
        if (t == null) return null;
        return node(t.val, copy(t.left), copy(t.right));
    }

    static TreeNode merge(TreeNode a, TreeNode b) {
        if (a == null && b == null) return null;
        if (b == null) return copy(a);
        if (a == null) return copy(b);
        return node(a.val + b.val, merge(a.left, b.left), merge(a.right, b.right));
    }

    static String show(TreeNode t) {
        if (t == null) return "_";
        if (t.left == null && t.right == null) return String.valueOf(t.val);
        return t.val + "(" + show(t.left) + ", " + show(t.right) + ")";
    }

    public static void main(String[] args) {
        TreeNode a = node(1, node(3, leaf(5), null), leaf(2));
        TreeNode b = node(2, node(1, null, leaf(4)), node(3, null, leaf(7)));
        System.out.println(show(merge(a, b)));
    }
}

Output

3(4(5, 4), 5(_, 7))

Time: O(m + n): every node of both trees is visited or copied. Space: O(m + n) for the new tree.

Optimal: reuse the first tree's nodes

Where both trees have a node, add the second node's value into the first and merge the children. Where only one tree has a subtree, attach that whole subtree to the result by reference: no copying, and no visiting its nodes. The result reuses nodes of both inputs, so the first tree is modified and the inputs must not be used separately afterwards.

Java

public class Main {
    static class TreeNode {
        int val;
        TreeNode left, right;
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    static TreeNode node(int val, TreeNode left, TreeNode right) {
        return new TreeNode(val, left, right);
    }

    static TreeNode leaf(int val) {
        return new TreeNode(val, null, null);
    }

    static TreeNode merge(TreeNode a, TreeNode b) {
        if (a == null) return b;
        if (b == null) return a;
        a.val += b.val;
        a.left = merge(a.left, b.left);
        a.right = merge(a.right, b.right);
        return a;
    }

    static String show(TreeNode t) {
        if (t == null) return "_";
        if (t.left == null && t.right == null) return String.valueOf(t.val);
        return t.val + "(" + show(t.left) + ", " + show(t.right) + ")";
    }

    public static void main(String[] args) {
        TreeNode a = node(1, node(3, leaf(5), null), leaf(2));
        TreeNode b = node(2, node(1, null, leaf(4)), node(3, null, leaf(7)));
        System.out.println(show(merge(a, b)));
        System.out.println(show(merge(null, leaf(8))));
    }
}

Output

3(4(5, 4), 5(_, 7))
8

Time: O(min(m, n)): only the positions where both trees have a node are visited. Space: O(h) for the recursion; no nodes are allocated.

a.val += b.val changes the first tree's node in place. The matching node of the second tree is dropped from the result, and the garbage collector reclaims it once nothing refers to it.

Edge cases

One tree empty: the other tree is returned as it is.
Different shapes: subtrees present in only one tree are attached unchanged.