0

I was looking at minimum sum subtree problem and came up with recursion solution:

public class Solution {
    /**
     * @param root: the root of binary tree
     * @return: the root of the minimum subtree
     */

    int minSoFar;
    public TreeNode findSubtree(TreeNode root) {
        TreeNode minNode = root;

        minSoFar = Integer.MAX_VALUE;
        subtreeSum(root,minNode);
        return minNode;
    }

    //return sum of the tree at root
    private int subtreeSum(TreeNode root, TreeNode minNode){
        if(root == null){
            return 0;
        }

        int sum = root.val + subtreeSum(root.left,minNode) + subtreeSum(root.right,minNode);

        if(sum < minSoFar){
            minNode = root;
            minSoFar = sum;
        }

        return sum;
    }

}

However the minNode does not get updated during the recursive calls, what is the reason for that? if I change minNode to a global variable it would work. I couldn't figure out where went wrong.

mz999
  • 53
  • 3
  • 1
    Can you describe the "minimum sum subtree problem" please? Java is pass by value, so `minNode` inside `subtreeSum` is just a local variable. You can wrap it in a container or make it a class var (the former is safer). – ggorlen May 22 '20 at 02:28
  • 1
    Java is pass-by-value. It has no such thing as 'pass by object address',and this isn't an example of it. And if it was it still wouldn't work, as you would need pass-by-reference-to-object-address. – user207421 May 22 '20 at 02:42
  • 1
    Thanks guys. I didn't grasp the concept that it's just a copy that has the same memory address, if I change the reference (not the field) it does not reflect back to the previous function. Thanks! – mz999 May 22 '20 at 03:16

0 Answers0