< Back




938. Range Sum of BST

We're given the root of a binary search tree and two integers, high and low. We're asked to find the
sum of all nodes in the binary search tree that are in the range [low, high], inclusive.

To solve this, we use depth-first search. At each node, we check to see if its value is in the
inclusive [low, high] range. If so, we add its value to the answer. If the node is greater than
low, we know that more nodes on the left subtree of the current node can possibly be in the range,
so we add the left node to the stack. Similarly, if the node is less than high, we know that nodes
on the right subtree are possibly in range - so we add the right node to the stack.

The solution is as follows:


  class Solution:
      def rangeSumBST(self, root: Optional[TreeNode], low: int, high: int) -> int:
          ans = 0
          if not root:
              return ans
          stack = [root]

          while stack:
              node = stack.pop()

              if low <= node.val and node.val <= high:
                  ans += node.val

              if low < node.val:
                  if node.left:
                      stack.append(node.left)

              if node.val < high:
                  if node.right:
                      stack.append(node.right)

          return ans


_ Time Complexity:

  O(n) - We inspect all nodes in the binary search tree.

_ Space Complexity:

  O(n) - We maintain a stack of nodes to visit.