Range Sum of BST

Range Sum of BST

What is this problem about?

The Range Sum of BST problem asks you to find the sum of all node values in a Binary Search Tree that fall within a given range [low, high]. This easy coding problem uses BST-aware DFS — pruning subtrees that are entirely out of range. The binary search tree, DFS, binary tree, and tree interview pattern is demonstrated.

Why is this asked in interviews?

Microsoft, Meta, Amazon, Google, Bloomberg, and Adobe ask this because it tests understanding of BST properties — specifically that you can prune entire subtrees (left subtree if node > high, right subtree if node < low). This makes the solution more efficient than a full traversal.

Algorithmic pattern used

BST-aware DFS with pruning. At each node: if node.val > high, go only left (all right subtree values too large). If node.val < low, go only right (all left subtree values too small). If in range, add to sum and traverse both children.

Example explanation

BST: root=10, left=5(3,7), right=15(13,18). Range=[7,15].

• 10 in [7,15]: add 10. Go both.
• 5 < 7: go right only. 7 in range: add 7. Both children null.
• 15 in [7,15]: add 15. Go both. 13 in range: add 13. 18 > 15: go left only (null). Sum = 10+7+15+13 = 45.

Common mistakes candidates make

• Not using BST properties (traversing all nodes unnecessarily).
• Pruning left instead of right when node > high.
• Confusing low/high direction (left subtree has smaller values, right has larger).
• Not handling null nodes.

Interview preparation tip

Range Sum of BST is the gateway to BST-aware algorithms. The core property: left subtree < node < right subtree. This enables directional pruning. Practice: "k-th smallest in BST," "count nodes in BST range," "sum of BST nodes." Each uses the same BST pruning logic. BST traversal is a fundamental skill tested at every major tech company.