Range Sum of BST - Video Solutions

Problem Overview: Given the root of a Binary Search Tree and two integers low and high, return the sum of all node values that fall within the inclusive range [low, high]. The BST property helps avoid visiting nodes that cannot contribute to the sum.

Approach 1: Recursive In-Order Traversal (O(n) time, O(h) space)

This approach performs a classic in-order traversal (left → node → right) using recursion. Because the tree is a binary search tree, values in the left subtree are smaller and values in the right subtree are larger. While traversing, add the node value to the total if it falls inside [low, high]. You can also prune branches: if node.val < low, skip the left subtree; if node.val > high, skip the right subtree. The traversal visits each relevant node once, giving O(n) time in the worst case and O(h) recursion stack space, where h is the tree height.

This method is simple and expressive. Recursion naturally fits problems involving depth-first search on trees, and the BST ordering allows early pruning that reduces unnecessary work in balanced trees.

Approach 2: Iterative In-Order Traversal Using Stack (O(n) time, O(h) space)

The iterative version simulates recursion with an explicit stack. Start from the root and push nodes while moving left. Pop the top node, process its value, then move to its right subtree. During processing, add the node’s value to the running sum if it lies within [low, high]. Just like the recursive version, the BST ordering can be used to skip subtrees that cannot contain valid values.

The stack holds at most h nodes at a time, giving O(h) space complexity. The algorithm still visits each node at most once, resulting in O(n) time complexity. Choose this approach if you want to avoid recursion depth limits or prefer explicit control of traversal state.

Recommended for interviews: The recursive DFS solution is typically expected because it clearly expresses tree traversal logic and shows you understand the BST ordering optimization. Mentioning subtree pruning based on low and high demonstrates deeper knowledge of tree problems. The iterative stack approach is a solid alternative when recursion is restricted.