0938.md

938. Range Sum of BST

Level:

Topic:

Question

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

Input: root = [10,5,15,3,7,null,18], low = 7, high = 15
Output: 32
Explanation: Nodes 7, 10, and 15 are in the range [7, 15]. 7 + 10 + 15 = 32.

Intuition

Since it's a BST, all of the left subtree nodes must be less than current node and right subtree nodes must be greater than current node

Recursive:

• Base case: for traversal, if the node is null, return
• if the current node value is >= low and <= high, add to sum
• if the current node value is < low, don't check the left
  • meaning if the current node value is > low, check for its left subtree
• if the current node value is > high, don't check the right
  • if the current node value is < high, check its right subtree

Iterative:

• use a queue or stack to store the current node

Code

Time: O(n)
Space: O(n)

Recursive

public int rangeSumBST(TreeNode root, int low, int high) {
    if (root == null)
        return 0;

    int sum = 0;
    if (root.val >= low && root.val <= high)
        sum += root.val;

    if (root.val > low)
        sum += rangeSumBST(root.left, low, high);

    if (root.val < high)
        sum += rangeSumBST(root.right, low, high);
    return sum;
}
// or
int sum = 0;
public int rangeSumBST(TreeNode root, int low, int high) {
    helper(root, low, high);
    return sum;
}

private void helper(TreeNode root, Integer low, Integer high) {
    if (root == null)
        return ;

    if (root.val >= low && root.val <= high)
        sum += root.val;

    if (root.val > low)
        helper(root.left, low, high);
    if (root.val < high)
        helper(root.right, low, high);
}

Iterative

public int rangeSumBST(TreeNode root, int low, int high) {
    int sum = 0;

    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);

    while (!queue.isEmpty()) {
        root = queue.poll();
        if (root == null) continue;
        if (root.val <= high && root.val >= low)
            sum += root.val;

        if (root.val > low)
            queue.add(root.left);
        if (root.val < high)
            queue.add(root.right);
    }

    return sum;
}