💬 Discord
Sign In
NeetCode #395LC-938EasyTrees
← Back to All Problems

#395 · #938 · Range Sum of BST(二叉搜索树的范围和)

📌 Problem Statement & Constraints

Given the root of a binary search tree and two integers low and high, return the sum of all values in the inclusive range [low, high]. Constraints: the number of nodes is in [1, 2 * 10^4], 1 <= Node.val <= 10^5, 1 <= low <= high <= 10^5.

💡 Core Algorithmic Approaches

  1. Exploit the BST ordering to prune the traversal.
  2. If the node's value is below low, the entire left subtree is also below low, so only recurse right.
  3. If the value is above high, only recurse left.
  4. Otherwise include the value and recurse into both subtrees.

💻 Benchmark Python3 Implementation

class Solution:
    def rangeSumBST(self, root: Optional[TreeNode], low: int, high: int) -> int:
        if not root:
            return 0
        if root.val < low:
            return self.rangeSumBST(root.right, low, high)   # left subtree is all too small
        if root.val > high:
            return self.rangeSumBST(root.left, low, high)    # right subtree is all too large
        return (root.val
                + self.rangeSumBST(root.left, low, high)
                + self.rangeSumBST(root.right, low, high))

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n) worst case, but typically much less because whole subtrees are pruned.
💾 Space Complexity
O(h) for the recursion stack.

⚠️ Interview Pitfalls & Follow-ups

  • Traversing the whole tree unconditionally: correct but misses the BST pruning that is the point of the problem.
  • Pruning with <= instead of <: the bounds are inclusive, so a node equal to low or high must be included.
  • Recursing into both subtrees when one is prunable: that defeats the optimisation.
  • Assuming the tree is balanced: the worst case is still O(n).