Why don't updates to Map.Entry in a Java child method reflect in the parent method, when passed around as state?

Question

I am trying to solve a simple leetcode problem. The question is a tree-problem , asking us to return the deepest leaves sum. https://leetcode.com/problems/deepest-leaves-sum/description/

I used DFS to solve this problem. I pass a level variable as one of the inputs to the recursive DFS call. I report the result (if the level is indeed deeper than or equal to what we have seen before) at the leaf node (base case). I used a Map.Entry<Integer, Integer> to hold the result - which maps the deepest level to its respective sum.

What I notice is when I declare this Map.Entry<> as a global class level variable, the methods reflect the updates made to it correctly. But when I initialize it to null in the parent function and pass it around as state in the dfs call, trying to update it at the leaf nodes - the changes don't reflect in the main method.

I am struggling to understand why?

This works

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {

    Map.Entry<Integer, Integer> deepestLevelSum; 

    public int deepestLeavesSum(TreeNode root) {
        if (root.left == null && root.right == null)
            return root.val;
        deepestLevelSum = null;
        dfsHelper(root, 0);
        return deepestLevelSum.getValue();
    }

    private void dfsHelper(TreeNode root, int level){
        //report result if valid
        if (root.left == null && root.right == null) {
            if (deepestLevelSum == null || deepestLevelSum.getKey() < level) {
                deepestLevelSum = new HashMap.SimpleEntry(level, root.val);     
            } else if (deepestLevelSum.getKey() == level){
                deepestLevelSum.setValue(deepestLevelSum.getValue()+root.val);
            }
        } else {
            if (root.left != null) 
                dfsHelper(root.left, level+1);
            if (root.right != null)
                dfsHelper(root.right, level+1);
        }
    }
}

But this doesn't. Changes made to Map.Entry<Integer, Integer> deepestLevelSum variable in the dfs call, doesn't get reflected in the main (parent) method.

class Solution {

    public int deepestLeavesSum(TreeNode root) {
        if (root.left == null && root.right == null)
            return root.val;
        Map.Entry<Integer, Integer> deepestLevelSum = new HashMap.SimpleEntry(0, root.val); 
        dfsHelper(root, 0, deepestLevelSum);
        return deepestLevelSum.getValue();
    }

    private void dfsHelper(TreeNode root, int level, Map.Entry<Integer, Integer> deepestLevelSum){
        //report result if valid
        if (root.left == null && root.right == null) {
            if (deepestLevelSum == null || deepestLevelSum.getKey() < level) {
                deepestLevelSum = new HashMap.SimpleEntry(level, root.val);     
            } else if (deepestLevelSum.getKey() == level){
                deepestLevelSum.setValue(deepestLevelSum.getValue()+root.val);
            }
        } else {
            if (root.left != null) 
                dfsHelper(root.left, level+1, deepestLevelSum);
            if (root.right != null)
                dfsHelper(root.right, level+1, deepestLevelSum);
        }
    }
}

As far as I understand, the entry is mutable - that's why we have the setValue() method, but am I missing something in my basic understanding of pass-by-reference?

Answer 1

In Java, when you pass an object as a parameter to a method, you are actually passing a copy of the reference to that object.

So, when you reassign deepestLevelSum with

deepestLevelSum = new HashMap.SimpleEntry(level, root.val);

 

you are assigning a new reference to the local deepestLevelSum variable within the method, but it does not affect the original reference outside the method ence why

return deepestLevelSum.getValue();

doesn't return the value you expected.

In the end, what you are doing is "overwriting" the reference copy you have, while what you were expecting is "overwriting" the object to which the reference leads.

Hope this is clear