#938

Easy

auto_awesomeBinary-tree traversal and state tracking

LeetCode Problem Workspace

Range Sum of BST

Given a BST and a range, calculate the sum of all node values within that range.

tree depth first search binary search tree binary tree

Problem Statement

You are given the root of a binary search tree (BST) and two integers, low and high. Your task is to return the sum of the values of all nodes whose value is in the inclusive range [low, high].

The binary search tree is structured such that for each node, all values in the left subtree are smaller than the node's value, and all values in the right subtree are greater. Efficient traversal methods are needed to minimize unnecessary checks and computations.

Examples

Example 1

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

Output: 32

Nodes 7, 10, and 15 are in the range [7, 15]. 7 + 10 + 15 = 32.

Example 2

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

Output: 23

Nodes 6, 7, and 10 are in the range [6, 10]. 6 + 7 + 10 = 23.

Constraints

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

Solution Approach

DFS Traversal

Perform a Depth-First Search (DFS) on the tree. At each node, check if its value falls within the range. If so, add it to the sum. If the node's value is greater than the high bound, only explore the left subtree, and vice versa for the low bound.

Early Pruning

Leverage the properties of a BST to prune unnecessary branches. If a node's value is smaller than the low bound, skip its left subtree, and if it’s greater than the high bound, skip the right subtree. This reduces the traversal overhead.

Iterative Approach

Instead of recursion, an iterative approach using a stack can be employed to simulate the DFS traversal. This may help in avoiding deep recursion issues, especially in trees with high depth.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity is O(N), where N is the number of nodes in the tree. Each node is visited at most once. The space complexity is O(H), where H is the height of the tree, which accounts for the space used by the recursion stack or the stack used in the iterative approach.

What Interviewers Usually Probe

Can the candidate optimize the traversal to reduce redundant checks?
Does the candidate demonstrate understanding of tree pruning based on BST properties?
Can the candidate implement both recursive and iterative solutions efficiently?

Common Pitfalls or Variants

Common pitfalls

Ignoring the BST properties and performing unnecessary traversal of both subtrees even when pruning is possible.
Misunderstanding the range inclusion, potentially excluding or including the bounds incorrectly.
Failing to handle deep recursion or stack overflow issues in large trees when using recursion.

Follow-up variants

Consider solving the problem using a breadth-first search (BFS) approach.
What if the tree is not a BST? How would you adjust the approach?
How does the solution change if the range is dynamically updated during traversal?

FAQ

What is the primary approach for solving the Range Sum of BST problem?

The primary approach is to perform a DFS traversal while leveraging the BST properties to prune unnecessary branches and compute the sum of nodes within the given range.

How do we handle large trees with deep recursion in this problem?

You can implement the solution iteratively using a stack to avoid deep recursion and prevent stack overflow issues in large trees.

Can we solve the Range Sum of BST problem using a BFS approach?

While DFS is the most common approach, BFS can also be used, especially in situations where level-wise processing of the tree is needed.

What are some common pitfalls when solving Range Sum of BST?

Common pitfalls include failing to properly prune unnecessary branches, incorrectly handling range bounds, and facing stack overflow issues due to deep recursion.

How can GhostInterview help with this problem?

GhostInterview guides users through optimizing the traversal, reinforcing understanding of pruning, and ensuring efficient implementation with both recursive and iterative solutions.

terminal

Solution

Solution 1: DFS

We design a function $dfs(root)$, which represents the sum of the values of all nodes in the subtree with $root$ as the root, and the values are within the range $[low, high]$. The answer is $dfs(root)$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

# 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
class Solution:
    def rangeSumBST(self, root: Optional[TreeNode], low: int, high: int) -> int:
        def dfs(root: Optional[TreeNode]) -> int:
            if root is None:
                return 0
            x = root.val
            ans = x if low <= x <= high else 0
            if x > low:
                ans += dfs(root.left)
            if x < high:
                ans += dfs(root.right)
            return ans

        return dfs(root)

Continue Practicing

#897 increasing order search tree #1038 binary search tree to greater sum tree #783 minimum distance between bst nodes