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. You need to return the sum of values of all nodes with a value in the inclusive range [low, high].

Clarifying Questions

1. Q: What is the range of the integers in the tree and the values of low and high?
   • A: The problem constraints (in a typical environment) will ensure that these values are within the bounds of a 32-bit signed integer.
2. Q: Is the BST provided always valid and properly structured?
   • A: Yes, you can assume the tree will always be a valid Binary Search Tree.
3. Q: Can the BST have duplicate values?
   • A: No, typically BSTs do not contain duplicate values.
4. Q: Can the tree be empty?
   • A: Yes, the tree can be empty. If it is, the function should return 0.

Strategy

1. Traversal Method Selection:
   • Since this is a BST, properties of BST should be leveraged. For this problem, Depth-First Search (DFS) approach using recursion is suitable. We could also use a stack for iterative DFS, but recursive DFS simplifies the implementation.
2. Condition Checks:
   • Traverse the tree and for each node:
     • If the node’s value is within the range [low, high], add its value to the sum.
     • If the node’s value is greater than low, there might be nodes in the left subtree within the range, so explore the left subtree.
     • If the node’s value is less than high, there might be nodes in the right subtree within the range, so explore the right subtree.
3. Base Case:
   • If the current node is null, return 0 since it does not contribute to the sum.

Code

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int rangeSumBST(TreeNode root, int low, int high) {
        // If the current node is null, return 0 as there's no value to add
        if (root == null) {
            return 0;
        }

        // Initialize the sum to 0
        int sum = 0;

        // If the current node's value is within the range, add it to the sum
        if (root.val >= low && root.val <= high) {
            sum += root.val;
        }

        // If the current node's value is greater than low, check the left subtree
        if (root.val > low) {
            sum += rangeSumBST(root.left, low, high);
        }

        // If the current node's value is less than high, check the right subtree
        if (root.val < high) {
            sum += rangeSumBST(root.right, low, high);
        }

        // Return the computed sum
        return sum;
    }
}

Time Complexity

• Time Complexity: O(N), where N is the number of nodes in the BST. In the worst case, we may need to visit all nodes.
• Space Complexity: O(H), where H is the height of the BST. This accounts for the recursive call stack, which in the worst case of an unbalanced tree could be O(N) (typically O(log N) for balanced trees).

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

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?