Python BST Range Sum Function Not Returning Expected Results Will Using Local Variable

Question

I'm currently working on a Python function that's supposed to calculate the sum of values in a Binary Search Tree (BST) within a given range. However, my code doesn't seem to be working as expected. I'd appreciate some guidance on what might be going wrong.

Here's the code for the Solution class I'm using:

class Solution:
    def rangeSumBST(self, root, low: int, high: int) -> int:
        def dfs(root):
            if root is None:
                return 0
            c = 0
            if low <= root.val <= high:
                c += root.val
            dfs(root.left)
            dfs(root.right)
            return c
        return dfs(root)

The idea is to perform a Depth-First Search (DFS) on the BST and add values to the sum c if they fall within the given range (low to high). However, it's not returning the correct result.

I've tried to debug this code, but I can't figure out what's causing the issue. Is there something obvious I'm missing in my implementation, or is there a logical error in my code that's leading to incorrect results?

Any help or suggestions to resolve this issue would be greatly appreciated. Thanks in advance!

Answer 1

Your code is calling dfs but not doing anything with the returning values. You should add them to the sum instead:

class Solution:
    def rangeSumBST(self, root, low: int, high: int) -> int:
        def dfs(root):
            if root is None:
                return 0
            c = dfs(root.left) + dfs(root.right)
            if low <= root.val <= high:
                c += root.val
            return c
        return dfs(root)