algoadvance

Given the root of a Binary Search Tree (BST) and two integers low and high, return the sum of the 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: The nodes with values 7, 10, and 15 are in the range [7, 15]. They sum up to 32.
2. Input: root = [10, 5, 15, 3, 7, 13, 18, 1, null, 6], low = 6, high = 10
   • Output: 23
   • Explanation: The nodes with values 6, 7, and 10 are in the range [6, 10]. They sum up to 23.

Clarifying Questions

1. Is the input tree always a valid BST?
   • Yes, the problem guarantees that the tree is a valid BST.
2. Are the values of the nodes always integers?
   • Yes, the problem specifies the integer node values.
3. Can the input tree include negative values?
   • The problem does not specify, but typically, node values can be negative integers.
4. Are low and high always within the range of node values?
   • Yes, low and high are integers, and they are used to find nodes within a specified range.

Strategy

Given that it’s a BST, properties like the left subtree having smaller values and the right subtree having larger values can be leveraged to efficiently navigate the tree:

1. Traversal Approach: An In-Order DFS (Depth-First Search) will ensure visiting nodes in non-decreasing order.

2. Optimization:
   • If the current node’s value is less than low, skip the left subtree because all values there will also be less than low.
   • If the current node’s value is greater than high, skip the right subtree because all values there will also be greater than high.
3. DFS Implementation:
   • If the current node value is within [low, high], add it to the sum.
   • Recursively check the left and right subtrees based on the comparison with low and high.

Code

# 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

def rangeSumBST(root: TreeNode, low: int, high: int) -> int:
    def dfs(node: TreeNode) -> int:
        if not node:
            return 0
        if node.val < low:
            # Only right subtree could have nodes in range
            return dfs(node.right)
        elif node.val > high:
            # Only left subtree could have nodes in range
            return dfs(node.left)
        else:
            # Current node is in range, check both subtrees
            return node.val + dfs(node.left) + dfs(node.right)
    
    return dfs(root)

Time Complexity

• Best-case: O(n), where n is the number of nodes in the BST.
  • This happens in cases where all nodes’ values are within the range [low, high].
• Average-case: O(h), where h is the height of the BST.
  • In a balanced BST, h ≈ log(n).

This time complexity is efficient given the properties of the BST and the constraints of the problem.

Try our interview co-pilot at AlgoAdvance.com

• 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?