algoadvance

Leetcode 938. Range Sum of BST

Problem Statement

You are given the root of a binary search tree (BST) and two integers low and high. Return the sum of values of all nodes with a value in the inclusive range [low, high].

Example:

Input: root = [10,5,15,3,7,null,18], low = 7, high = 15
Output: 32
Explanation: Nodes within range are [10, 7, 15]. Sum is 32.

Clarifying Questions

  1. What is the range of node values?
    • Node values are usually within the 32-bit integer range unless otherwise specified.
  2. Can the BST have duplicate values?
    • Typically, a BST does not have duplicate values.
  3. What is the maximum size of the tree?
    • Constraints typically specify the size, but if not provided, consider reasonable assumptions for computational limits.
  4. Are the low and high values always valid?
    • Assume they are valid and low <= high.

Strategy

To solve this problem, leverage the properties of the Binary Search Tree:

  1. Recursion: Traverse the tree and keep a running sum of values within the range.
    • If the current node’s value is within [low, high], add it to the sum.
    • If the current node’s value is less than low, explore only the right subtree.
    • If the current node’s value is greater than high, explore only the left subtree.
    • Otherwise, explore both subtrees.

Code

#include <iostream>

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    int rangeSumBST(TreeNode* root, int low, int high) {
        if (!root) {
            return 0;  // Base case: if the node is null, return 0
        }

        // Initialize the sum
        int sum = 0;
        
        // Case 1: Node's value is within the range
        if (root->val >= low && root->val <= high) {
            sum += root->val;
        }

        // Case 2: Node's value is greater than low, explore left subtree
        if (root->val > low) {
            sum += rangeSumBST(root->left, low, high);
        }

        // Case 3: Node's value is less than high, explore right subtree
        if (root->val < high) {
            sum += rangeSumBST(root->right, low, high);
        }
        
        return sum;
    }
};

// Helper function to create a new node
TreeNode* newNode(int data) {
    TreeNode* node = new TreeNode();
    node->val = data;
    node->left = node->right = nullptr;
    return node;
}

// Main function to test the solution
int main() {
    // Creating the tree from the example
    /* Tree:
            10
           /  \
          5    15
         / \     \
        3   7     18
    */
    TreeNode* root = newNode(10);
    root->left = newNode(5);
    root->right = newNode(15);
    root->left->left = newNode(3);
    root->left->right = newNode(7);
    root->right->right = newNode(18);

    Solution sol;
    int low = 7, high = 15;
    std::cout << "Range Sum of BST (7, 15): " << sol.rangeSumBST(root, low, high) << std::endl;  // Output: 32

    return 0;
}

Time Complexity

This solution effectively leverages the BST properties to minimize unnecessary traversals, ensuring efficient computation of the range sum.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI