Write a program to merge two binary trees. Each node in the new tree should hold a value equal to the sum of the values of the corresponding nodes of the input trees. If only one input tree has a node in a given position, the corresponding node in the new tree should match that input node.

By | January 16, 2024

Asked by SalesForce

JavaScript:

class TreeNode {
    constructor(val, left = null, right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

function mergeTrees(t1, t2) {
    if (!t1) return t2;
    if (!t2) return t1;

    t1.val += t2.val;
    t1.left = mergeTrees(t1.left, t2.left);
    t1.right = mergeTrees(t1.right, t2.right);

    return t1;
}

// Example usage:
// Assuming you have two trees, tree1 and tree2
// mergedTree = mergeTrees(tree1, tree2);

Java:

class TreeNode {
    int val;
    TreeNode left, right;

    public TreeNode(int val) {
        this.val = val;
    }
}

public class BinaryTreeMerger {
    public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
        if (t1 == null) return t2;
        if (t2 == null) return t1;

        t1.val += t2.val;
        t1.left = mergeTrees(t1.left, t2.left);
        t1.right = mergeTrees(t1.right, t2.right);

        return t1;
    }

    // Example usage:
    // Assuming you have two trees, tree1 and tree2
    // TreeNode mergedTree = mergeTrees(tree1, tree2);
}

Python:

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def merge_trees(t1, t2):
    if not t1:
        return t2
    if not t2:
        return t1

    t1.val += t2.val
    t1.left = merge_trees(t1.left, t2.left)
    t1.right = merge_trees(t1.right, t2.right)

    return t1

# Example usage:
# Assuming you have two trees, tree1 and tree2
# merged_tree = merge_trees(tree1, tree2)

These programs define a TreeNode class and a function (mergeTrees in JavaScript, mergeTrees method in Java, and merge_trees function in Python) to merge two binary trees following the specified rules. You can adapt these examples based on your specific requirements.

Leave a Reply

Your email address will not be published. Required fields are marked *