Range Sum of BST using DFS

Question

Problem: Given the root node of a binary search tree, return the sum of values of all nodes with value between L and R (inclusive).

The binary search tree is guaranteed to have unique values.

Example 1:

Input: root = [10,5,15,3,7,null,18], L = 7, R = 15

Output: 32

Leetcode problem: https://leetcode.com/problems/range-sum-of-bst/

My approach: I'm trying to do a dfs and visit each node, if the value at that node fits the constraints then I want to return it in my recursive function. I then add up all the values and return that to my main function.

I'm still trying to understand recursion, what am I doing wrong in this code (why does it only return 10 and not 32?).

I'm trying to return a value from each recursive function and add it in the end - does that make sense to do?

/**
 * 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 {
    public int rangeSumBST(TreeNode root, int L, int R) {
        if(root == null) {
            return 0;
        }

        rangeBST(root, L, R);
        
        return rangeBST(root, L, R);
    }
    
    public static int rangeBST(TreeNode root, int L, int R) {
        if(root == null) {
            return 0;
        }
        
        if(root.val >= L && root.val <= R) {
            return root.val;
        }

        int x = rangeBST(root.left, L, R);
        int y = rangeBST(root.right, L, R);
        
        return x + y;
    }
}

Answer 1

Two issues:

• The algorithm should recur deeper when the value is between the L-R range, but instead your returns the current node's own value without looking any deeper.

• The algorithm should not always need to visit each node, but take advantage of the BST property: it should only search in the left subtree when the current value would not exclude to find any in-range values in that subtree.

  For instance, if the current node has value 3, and the L-R range is (5,9), then it makes no sense to look further in the left subtree, as there all values are guaranteed to be less than 3, no matter how big that subtree may be.

  A similar observation may hold for the right subtree.

class Solution {
    public int rangeSumBST(TreeNode root, int L, int R) {
        if (root == null) return 0;
        int val = 0;
        if (root.val >= L && root.val <= R) val += root.val;
        if (root.val < R) val += rangeSumBST(root.right, L, R);
        if (root.val > L) val += rangeSumBST(root.left, L, R);
        return val;
    }
}