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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Range Sum of BST

Difficulty: Easy

Problem Description

Given the root node of a binary search tree and two integers low and high, return the sum of values of all nodes with a value in the inclusive range [low, high].

Key Insights

  • The problem requires traversing a binary search tree (BST).
  • Since it's a BST, values to the left are less than the current node's value, and values to the right are greater.
  • We can skip entire branches of the tree if their values fall outside the range [low, high].
  • The algorithm can be implemented using Depth-First Search (DFS) or Breadth-First Search (BFS).

Space and Time Complexity

Time Complexity: O(N), where N is the number of nodes in the tree, as we may need to visit every node in the worst case. Space Complexity: O(H), where H is the height of the tree, due to recursive stack space (for DFS) or queue space (for BFS).

Solution

To solve the problem, we will use a Depth-First Search (DFS) approach, which will allow us to traverse the tree nodes recursively. We will keep a running sum of node values that fall within the specified range [low, high]. If a node's value is less than low, we can skip its left subtree. If it is greater than high, we can skip its right subtree. This approach leverages the properties of a binary search tree to efficiently compute the sum.

Code Solutions

def rangeSumBST(root, low, high):
    # Initialize the sum to 0
    total_sum = 0
    
    # Define the DFS function
    def dfs(node):
        nonlocal total_sum
        if not node:
            return
        
        # If the current node's value is within the range
        if low <= node.val <= high:
            total_sum += node.val
        
        # If the current node's value is greater than low, explore left subtree
        if node.val > low:
            dfs(node.left)
        
        # If the current node's value is less than high, explore right subtree
        if node.val < high:
            dfs(node.right)
    
    # Start DFS from the root
    dfs(root)
    return total_sum
← Back to All Questions