Range Sum of BST - Practice Coding Problems

Range Sum of BST - Problem

Given the root node of a binary search tree and two integers low and high, return the sum of values of all nodes with a value in the inclusive range [low, high].

A Binary Search Tree (BST) is a tree where for every node, all values in the left subtree are smaller than the node's value, and all values in the right subtree are greater than the node's value.

Input & Output

Example 1 — Basic BST

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

› Output: 32

💡 Note: Nodes 7, 10, and 15 are in range [7,15]. Sum = 7 + 10 + 15 = 32

Example 2 — Smaller Range

$ Input: root = [10,5,15,3,7,13,18,1,null,6], low = 6, high = 10

› Output: 23

💡 Note: Nodes 6, 7, and 10 are in range [6,10]. Sum = 6 + 7 + 10 = 23

Example 3 — Single Node

$ Input: root = [5], low = 3, high = 8

› Output: 5

💡 Note: Only node 5 exists and it's in range [3,8]. Sum = 5

Constraints

The number of nodes in the tree is in the range [1, 2 × 10⁴]
1 ≤ Node.val ≤ 10⁵
1 ≤ low ≤ high ≤ 10⁵

Visualization

Tap to expand

Understanding the Visualization

Input BST

Binary Search Tree with range [7, 15]

Find Range

Identify nodes with values in [7, 15]

Sum Values

Add up all qualifying node values

Key Takeaway

🎯 Key Insight: Use BST property to prune subtrees that cannot contain values in the target range

Asked in

f Facebook 45 a Amazon 32 M Microsoft 28 G Google 25

The key insight is to leverage the BST property to skip entire subtrees when their values cannot be in our target range. The optimal approach uses DFS with pruning: if current node > high, skip right subtree; if current node < low, skip left subtree. Time: O(n), Space: O(h).

Common Approaches

Approach	Time	Space	Notes
✓ Optimized DFS with BST Pruning	O(n)	O(h)	Use BST property to skip unnecessary subtrees
Brute Force DFS	O(n)	O(h)	Visit every node and add values in range

Optimized DFS with BST Pruning — Algorithm Steps

Check if current node is in range and add to sum
If node value > high, skip right subtree
If node value < low, skip left subtree
Recursively process remaining subtrees

Visualization

Tap to expand

Step-by-Step Walkthrough

Check Node

Check if current node is in range

Smart Pruning

Skip left if val < low, skip right if val > high

Efficient Sum

Only visit nodes that could be in range

Code -

solution.c — C

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

struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
};

struct TreeNode* createNode(int val) {
    struct TreeNode* node = malloc(sizeof(struct TreeNode));
    node->val = val;
    node->left = NULL;
    node->right = NULL;
    return node;
}

int solution(struct TreeNode* root, int low, int high) {
    if (!root) return 0;
    
    int total = 0;
    
    // Add current node if in range
    if (root->val >= low && root->val <= high) {
        total += root->val;
    }
    
    // Only traverse left if current value > low
    if (root->val > low) {
        total += solution(root->left, low, high);
    }
    
    // Only traverse right if current value < high
    if (root->val < high) {
        total += solution(root->right, low, high);
    }
    
    return total;
}

int main() {
    // For simplicity, assume a basic tree construction
    struct TreeNode* root = createNode(10);
    root->left = createNode(5);
    root->right = createNode(15);
    root->left->left = createNode(3);
    root->left->right = createNode(7);
    root->right->right = createNode(18);
    
    int low = 7, high = 15;
    int result = solution(root, low, high);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

In worst case (unbalanced tree with all nodes in range), visits all nodes

✓ Linear Growth

Space Complexity

O(h)

Recursion stack depth equals tree height h

✓ Linear Space

125.0K Views

Medium Frequency

~15 min Avg. Time

3.4K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Optimized DFS with BST Pruning — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler