Range Sum of BST

This question looks like a plain “add up some numbers” task. And you can solve it that way. But the interviewer is hoping you notice something. The tree’s shape lets you skip whole branches you do not need. Spotting that skip is the real point of this question.

🎯 The Problem

You get a binary search tree and two numbers, low and high. A binary search tree, or BST, is a tree where every node’s left side holds smaller values and its right side holds larger values. Add up the values of all nodes that fall in the range.

The rules:

• You are given the root of a BST and two numbers, low and high.
• Add up the value of every node whose value sits between low and high.
• The range includes both ends. So low and high count too.
• Return that sum.

Input:  root = [10, 5, 15, 3, 7, null, 18], low = 7, high = 15
Output: 32

         10
        /  \
       5    15
      / \     \
     3   7     18

Explanation: Nodes in [7, 15] are 7, 10, and 15. Their sum is 7 + 10 + 15 = 32.

Look at which values fall inside 7 to 15. The 7, the 10, and the 15 are inside. The 3, the 5, and the 18 are outside. So we add 7 + 10 + 15 and get 32.

Here is the BST. Smaller values go left and larger values go right.

🐢 Approach 1: Visit Every Node (Brute Force)

Visit every node and test each one against the range.

The idea:

• Walk the whole tree, node by node.
• Order does not matter here.
• Test low <= value <= high at each node.

How it works:

• If the test is true, add the value to a total.
• At the end, return the total.

Why it is weak:

• It ignores the BST’s structure completely.
• It walks into branches it already knows are out of range.
• Anything below a node smaller than low can never be in range. Yet it still goes there.

Here is the visit-every-node code:

def range_sum_bst(root, low, high):
    if not root: return 0
    total = root.val if low <= root.val <= high else 0
    return total + range_sum_bst(root.left, low, high) + range_sum_bst(root.right, low, high)

⚡ Approach 2: Pruned Traversal (Best)

The idea in one line: use the BST rule to skip whole branches that cannot hold any in-range value.

The idea:

• Skipping a branch is called pruning. To prune means to cut off a part that cannot help.
• A node smaller than low has an even smaller left side. Skip the left.
• A node bigger than high has an even bigger right side. Skip the right.

How it works:

• Node smaller than low: go right only.
• Node bigger than high: go left only.
• Node inside the range: add it, then check both sides.

Why it is fast:

• You never walk into a branch the BST rule rules out.
• On a big tree that cuts out a huge amount of work.

This diagram shows the choice we make at each node based on its value.

Steps to Solve

1. If the node is empty, return zero.
2. If the node’s value is smaller than low, skip the left side and only go right.
3. If the node’s value is bigger than high, skip the right side and only go left.
4. If the node’s value is inside the range, add it to the sum.
5. For an in-range node, also add the results from both the left and right sides.
6. Return the total sum.

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int val;
    struct Node* left;
    struct Node* right;
} Node;

Node* newNode(int val) {
    Node* n = (Node*)malloc(sizeof(Node));
    n->val = val;
    n->left = NULL;
    n->right = NULL;
    return n;
}

int rangeSum(Node* node, int low, int high) {
    if (node == NULL) return 0;
    if (node->val < low) {                  // too small, go right only
        return rangeSum(node->right, low, high);
    }
    if (node->val > high) {                 // too big, go left only
        return rangeSum(node->left, low, high);
    }
    // in range: add this node and check both sides
    return node->val
         + rangeSum(node->left, low, high)
         + rangeSum(node->right, low, high);
}

int main(void) {
    Node* root = newNode(10);
    root->left = newNode(5);
    root->right = newNode(15);
    root->left->left = newNode(3);
    root->left->right = newNode(7);
    root->right->right = newNode(18);

    printf("%d\n", rangeSum(root, 7, 15));
    return 0;
}

32

#include <iostream>
using namespace std;

struct Node {
    int val;
    Node* left;
    Node* right;
    Node(int v) : val(v), left(nullptr), right(nullptr) {}
};

int rangeSum(Node* node, int low, int high) {
    if (!node) return 0;
    if (node->val < low) {                  // too small, go right only
        return rangeSum(node->right, low, high);
    }
    if (node->val > high) {                 // too big, go left only
        return rangeSum(node->left, low, high);
    }
    // in range: add this node and check both sides
    return node->val
         + rangeSum(node->left, low, high)
         + rangeSum(node->right, low, high);
}

int main() {
    Node* root = new Node(10);
    root->left = new Node(5);
    root->right = new Node(15);
    root->left->left = new Node(3);
    root->left->right = new Node(7);
    root->right->right = new Node(18);

    cout << rangeSum(root, 7, 15) << endl;
    return 0;
}

32

public class RangeSumBST {
    static class Node {
        int val;
        Node left, right;
        Node(int v) { val = v; }
    }

    public static int rangeSum(Node node, int low, int high) {
        if (node == null) return 0;
        if (node.val < low) {                  // too small, go right only
            return rangeSum(node.right, low, high);
        }
        if (node.val > high) {                 // too big, go left only
            return rangeSum(node.left, low, high);
        }
        // in range: add this node and check both sides
        return node.val
             + rangeSum(node.left, low, high)
             + rangeSum(node.right, low, high);
    }

    public static void main(String[] args) {
        Node root = new Node(10);
        root.left = new Node(5);
        root.right = new Node(15);
        root.left.left = new Node(3);
        root.left.right = new Node(7);
        root.right.right = new Node(18);

        System.out.println(rangeSum(root, 7, 15));
    }
}

32

class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None


def range_sum(node, low, high):
    if node is None:
        return 0
    if node.val < low:                  # too small, go right only
        return range_sum(node.right, low, high)
    if node.val > high:                 # too big, go left only
        return range_sum(node.left, low, high)
    # in range: add this node and check both sides
    return (node.val
            + range_sum(node.left, low, high)
            + range_sum(node.right, low, high))


root = Node(10)
root.left = Node(5)
root.right = Node(15)
root.left.left = Node(3)
root.left.right = Node(7)
root.right.right = Node(18)

print(range_sum(root, 7, 15))

32

class Node {
  constructor(val) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

function rangeSum(node, low, high) {
  if (node === null) return 0;
  if (node.val < low) {                 // too small, go right only
    return rangeSum(node.right, low, high);
  }
  if (node.val > high) {                // too big, go left only
    return rangeSum(node.left, low, high);
  }
  // in range: add this node and check both sides
  return (
    node.val +
    rangeSum(node.left, low, high) +
    rangeSum(node.right, low, high)
  );
}

const root = new Node(10);
root.left = new Node(5);
root.right = new Node(15);
root.left.left = new Node(3);
root.left.right = new Node(7);
root.right.right = new Node(18);

console.log(rangeSum(root, 7, 15));

32

Let us walk through the Python version line by line.

The function opens with if node is None: return 0. When we hit an empty spot there is nothing to add. So we return zero and that branch ends.

The line if node.val < low: return range_sum(node.right, low, high) is the first prune. The node is smaller than low, so the node itself is out of range. And everything on its left is even smaller, so it is also out of range. We skip the left side completely and only walk right. This is the work-saving part.

The next line if node.val > high: return range_sum(node.left, low, high) is the mirror prune. The node is bigger than high, so it is out of range. And everything on its right is even bigger. We skip the right side and only walk left.

If neither check stopped us, the node is inside the range. So the final return adds three things. It adds node.val, because this node counts. It adds the sum from the left side, because the left could hold more in-range values. And it adds the sum from the right side, for the same reason. All three together give the total for this node and everything under it.

Each return hands its sum up to the caller. So the root’s call collects the grand total, which we print.

⏱️ Time and Space Complexity

The brute force visits every node, so it is O(n) in time where n is the number of nodes. The pruned walk also has a worst case of O(n), because if the whole tree is inside the range you still visit everything. But in practice it skips many branches, so it usually visits far fewer nodes. For space, both use the call stack, which goes as deep as the tree. So the space is O(h), where h is the height. The real prize is the skipping, which cuts out branches the brute force wastes time on.

🧩 Key Takeaways

• ✅ A BST keeps smaller values on the left and larger values on the right.
• ✅ If a node is below low, its whole left side is too, so skip it.
• ✅ If a node is above high, its whole right side is too, so skip it.
• ✅ Add a node only when its value is inside the range.
• ✅ Pruning unneeded branches saves work compared to walking the whole tree.

🚀 What’s Next?

• Kth Smallest Element in a BST
• Validate Binary Search Tree