Range Sum of BST easy

Problem Statement

Given the root node 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 1

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

Example 2

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

Steps

1. Recursive Approach: We'll use a recursive function to traverse the BST.
2. Base Case: If the current node is null, we return 0 (no sum).
3. Check Range: If the current node's value is within the [low, high] range, we add its value to the sum.
4. Recursive Calls: We recursively call the function on the left and right subtrees. However, we can optimize this:
   • If the current node's value is less than low, we only need to explore the right subtree (since BST property ensures all smaller values are on the left).
   • If the current node's value is greater than high, we only need to explore the left subtree (since BST property ensures all larger values are on the right).

Explanation

The solution leverages the inherent property of a Binary Search Tree (BST): values in the left subtree are smaller than the current node's value, and values in the right subtree are larger. This allows us to prune unnecessary branches during the traversal, significantly improving efficiency. The recursive approach systematically explores the tree, adding the value of each node within the specified range to the total sum.

Code

using System;

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class Solution {
    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;
    }
}

Complexity

• Time Complexity: O(N) in the worst case, where N is the number of nodes in the BST. However, it's often better than O(N) due to the pruning of subtrees. In a balanced BST, it approaches O(logN) for search.
• Space Complexity: O(H) in the worst case, where H is the height of the BST. This is due to the recursive call stack. In a balanced BST, H is O(logN), while in a skewed BST, H is O(N).