Merging Binary Trees in Java

Question

I've been working on "Merge Two Binary Trees" for hours now, and I can't figure out why my code isn't working. I am given tree t1 as [1,3,2,5] and tree t2 as [2,1,3,null,4,null,7] and I have to merge the two trees by summing overlapping nodes and avoiding nulls where possible, so the result should be [3,4,5,5,4,null,7]. Rather than creating a new tree like I'm supposed to, I'm rewriting tree t1 to have the desired results. My code is as follows:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
        traversal(t1, t2);
        return t1;
    }

    public void traversal(TreeNode t1, TreeNode t2) {
        if(t2 == null) return;
        if(t1 == null)
            t1 = new TreeNode(0);
        t1.val += t2.val;
        traversal(t1.left, t2.left);
        traversal(t1.right, t2.right);
    }
}

My code runs with no errors, and my end result is [3,4,5,5], which is obviously wrong. It seems like the line

t1 = new TreeNode(0);

is not doing what I want it to do. I want it to change the current node from being null to having a value of 0, a null left node, and a null right node, so that in the next iteration, the program will iterate the newly created left node which is null.

I tried recreating the entire thing (including class / method declarations) in my IDE in order to play around with it and do some debugging, so I could edit my full code into this post if needed, but I also can't figure out how to do

TreeNode(int val, TreeNode left, TreeNode right) {
  this.val = val;
  this.left = left;
  this.right = right;
}

when I want either the left or the right (but not both) to be null, so my full code isn't as clean as it should be. In any case, can anyone help me figure out why my code is getting the wrong answer for the given input?

rxn1d rxn1d · Accepted Answer · 2020-04-01T03:24:24

I guess your problem here is that the code below doesn't really do what you intended to do.

public void traversal(TreeNode t1, TreeNode t2) {
. . .
if(t1 == null)
    t1 = new TreeNode(0);
. . .

Here you change your local copy of the reference to point to the new object. You don't change the original object. In fact, you cannot do that in a different method than the original method where an object was initially created. Please see java pass by value.

So basically you create a new TreeNode which is not connected to the parent node. You have to do it manually, keeping track of parent nodes as well.

Merging Binary Trees in Java

1 Answers