We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Range Sum of BST

Number: 975

Difficulty: Easy

Paid? No

Companies: Meta, Google, Amazon, Microsoft, Adobe

Problem Description

Given the root of a Binary Search Tree (BST) and two integers low and high, return the sum of values of all nodes that fall within the inclusive range [low, high]. Since the BST property holds, we can efficiently decide whether to explore the left subtree or the right subtree based on the current node's value.

Key Insights

  • Utilize the BST property to prune unnecessary branches (i.e., if a node's value is less than low, then its left subtree can be skipped; if greater than high, its right subtree can be skipped).
  • A Depth-First Search (DFS) traversal (recursive or iterative) is appropriate to visit only the relevant nodes.
  • Keep a running sum as you traverse nodes that fall within the range [low, high].

Space and Time Complexity

Time Complexity: O(n) in the worst-case scenario where every node is visited.
Space Complexity: O(n) in the worst-case due to recursive call stack or if an iterative approach uses a stack, especially in the case of a skewed tree.

Solution

We solve the problem using DFS traversal (recursion) leveraging the BST properties. At each node:

  1. If the node is null, return 0.
  2. If the node's value is within the range [low, high], add it to the sum.
  3. If the node's value is greater than low, explore the left subtree because it might contain nodes in range.
  4. If the node's value is less than high, explore the right subtree for potential nodes in range. This algorithm reduces unnecessary traversals by pruning off subtrees that cannot contribute to the result.

Code Solutions

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def rangeSumBST(self, root: TreeNode, low: int, high: int) -> int:
        # Base case: if the current node is None, return sum 0.
        if not root:
            return 0
        
        # Initialize sum for the current node.
        sum_val = 0
        
        # If the current node's value is within [low, high], add its value.
        if low <= root.val <= high:
            sum_val += root.val
        
        # If the current node's value is greater than low, explore left subtree.
        if root.val > low:
            sum_val += self.rangeSumBST(root.left, low, high)
        
        # If the current node's value is less than high, explore right subtree.
        if root.val < high:
            sum_val += self.rangeSumBST(root.right, low, high)
        
        return sum_val
← Back to All Questions