Range Sum Bst

81.Range Sum of BST

Tree

Depth-First Search

Problem Statement:

Given the root of a binary search tree (BST) and two integers L and R, return the sum of all values in the BST that fall within the range [L, R].

Algorithm:

1. If the tree is empty (root == null), return 0.
2. Initialize the sum as 0.
3. Check the current node’s value:
• If it lies within the range [L, R], add it to the sum.
• If the value is greater than or equal to L, recurse on the left subtree.
• If the value is less than or equal to R, recurse on the right subtree.
4. Return the sum of all values within the range.

Complexity:

Time: O(n), where n is the number of nodes in the tree | Space: O(h), where h is the height of the tree.

Java Implementation:

public int rangeSumBST(TreeNode root, int L, int R) {
    // Base case: if the tree is empty
    if (root == null) return 0;

    int sum = 0;

    // Add the current node's value if it is within the range
    if (root.val >= L && root.val <= R) sum += root.val;

    // Recurse on the left subtree if the current value is >= L
    if (root.val >= L) sum += rangeSumBST(root.left, L, R);

    // Recurse on the right subtree if the current value is <= R
    if (root.val <= R) sum += rangeSumBST(root.right, L, R);

    // Return the accumulated sum
    return sum;
}

Python Implementation:

def rangeSumBST(root, L, R):
    # Base case: if the tree is empty
    if not root:
        return 0

    # Initialize the sum
    sum = 0

    # Add the current node's value if it is within the range
    if L <= root.val <= R:
        sum += root.val

    # Recurse on the left subtree if the current value is >= L
    if root.val >= L:
        sum += rangeSumBST(root.left, L, R)

    # Recurse on the right subtree if the current value is <= R
    if root.val <= R:
        sum += rangeSumBST(root.right, L, R)

    # Return the accumulated sum
    return sum

C++ Implementation:

int rangeSumBST(TreeNode* root, int L, int R) {
    // Base case: if the tree is empty
    if (root == nullptr) return 0;

    int sum = 0;

    // Add the current node's value if it is within the range
    if (root->val >= L && root->val <= R) sum += root->val;

    // Recurse on the left subtree if the current value is >= L
    if (root->val >= L) sum += rangeSumBST(root->left, L, R);

    // Recurse on the right subtree if the current value is <= R
    if (root->val <= R) sum += rangeSumBST(root->right, L, R);

    // Return the accumulated sum
    return sum;
}