0

So I need to sum up all nodes in a BST within an inclusive range. For example, if the range is [7, 15] ('[' and ']' mean inclusive) for the example below,

    10
   /  \
  5    15
 / \     \
3   7    18

the sum would be 7 + 10 + 15 = 32

Here is my code below, I am doing a simple inOrderTraversal, but for some reason the resulting sum is 0.

class Solution {
    public int rangeSumBST(TreeNode root, int low, int high) {
        int sum = 0;
        helper(root, low, high, sum);
        return sum;
    }
    
    public void helper(TreeNode root, int low, int high, int sum) {
        
        if(root != null) {
            helper(root.left, low, high, sum);
            if(root.val >= low && root.val <= high) {
                System.out.println("sum before was " + sum);
                sum = sum + root.val;
                System.out.println("sum after was " + sum);
            }
            helper(root.right, low, high, sum);
        }
    }
}

Does anyone know why it is 0?

estel123
  • 11
  • 1

1 Answers1

1

The reason is that each function execution context of helper has its own sum variable. So any assignment to that variable will only affect that variable, not a variable of the caller which happens to have the same name.

Pass by value

Some languages have the concept of passing the reference of a variable, so that indeed such an integer would be shared by caller and callee, but in Java arguments are passed by value.

Return the value

In this case a solution is to make the recursive function return a sum: the sum that relates only to the nodes in the subtree rooted by that node. The caller can than add that returned sum to its own sum.

So that means you no longer need the extra sum parameter: sum can just be a local variable that starts with 0, to which the results from deeper calls are added, and which is finally returned to the caller.

This means the helper function will actually have the same signature as rangeSumBST, and so we could use rangeSumBST itself as recursive function.

Optimisation

Your naive in-order traversal can be optimised, by only visiting a child node when there is a chance its subtree has a node within range. If not, then don't visit it at all.

Here is a version of the function that takes these points into account:

class Solution {
    public int rangeSumBST(TreeNode root, int low, int high) {
        if (root == null) return 0;
        int val = 0;
        if (root.val >= low && root.val <= high) val += root.val;
        if (root.val < high) val += rangeSumBST(root.right, low, high);
        if (root.val >  low) val += rangeSumBST(root.left,  low, high);
        return val;
    }
}
trincot
  • 317,000
  • 35
  • 244
  • 286
  • Naming the parameter `root` is misleading, since most times it is called with a non-root node. – Andreas Jul 20 '21 at 21:28
  • @Andreas, every node is the root of its own subtree. It is in fact a good name, as the sum it calculates relates to *that* tree of which it is the root. – trincot Jul 20 '21 at 21:36
  • So why isn't the class named `TreeRoot`, if every node is a root. Sorry, I don't buy your argument. But, it's your answer, so you can name it as you will. – Andreas Jul 21 '21 at 00:13