Notebook

938. Range Sum of BST

Given the root node of a binary search tree, return the sum of values of all nodes with a value in the range [low, high].

Example 1:

Input: root = [10,5,15,3,7,null,18], low = 7, high = 15
Output: 32

Example 2:

Input: root = [10,5,15,3,7,13,18,1,null,6], low = 6, high = 10
Output: 23

Constraints:

The number of nodes in the tree is in the range [1, 2 * 10⁴].
1 <= Node.val <= 10⁵
1 <= low <= high <= 10⁵
All Node.val are unique.

Source

In [1]:

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

Code

In [2]:

def range_sum_bst(root, L, R):
    """DFS using a recursive approach"""
    def dfs(node):
        """similar to preorder traversal"""
        if not node:
            return

        nonlocal result
        if L <= node.val <= R:
            result += node.val
        if node.val > L:
            dfs(node.left)
        if node.val < R:
            dfs(node.right)

    result = 0
    dfs(root)
    return result

Follow up:

Solve it both recursively and iteratively.

Code

In [3]:

def range_sum_bst(root, L, R):
    """DFS using a recursive approach"""
    if not root:
        return 0

    stack = [root]
    result = 0
    while stack:
        node = stack.pop()
        if node is None:
            continue
        if L <= node.val <= R:
            result += node.val
        if node.val > L:
            stack.append(node.left)
        if node.val < R:
            stack.append(node.right)
    return result

In [ ]:

def range_sum_bst(root, L, R):
    """BFS using a recursive approach"""
    if not root:
        return 0

    queue = [root]
    result = 0
    for node in queue:
        if node is None:
            continue
        if L <= node.val <= R:
            result += node.val
        if node.val > L:
            queue.append(node.left)
        if node.val < R:
            queue.append(node.right)
    return result