Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

Range Sum Query

Problem Statement

Write a Java program that uses a Binary Search Tree (BST) to find the sum of all node values within a given range (e.g., between 20 and 60, inclusive). The program should use inorder traversal to collect values, leveraging the BST property to optimize by pruning branches outside the range. The implementation should reuse the BST node structure and test the range sum query with various trees and ranges, including edge cases like empty trees, ranges with no values in the tree, and ranges covering all or none of the tree’s values. You can visualize this as summing the ages of family members in a family tree whose ages fall within a specific range, using the tree’s ordered structure to efficiently skip irrelevant branches.

Input:

  • A BST represented by nodes with integer values.
  • Two integers, low and high, defining the inclusive range [low, high]. Output: An integer representing the sum of all node values within [low, high], and a string representation of the tree for clarity. Constraints:
  • The tree has between 0 and 10^5 nodes.
  • Node values, low, and high are integers in the range [-10^9, 10^9].
  • Duplicate values are not allowed in the BST.
  • low ≤ high. Example:
  • Input: Tree = [5, left: [3, left: [1], right: [4]], right: [7]], Range = [2, 6]
  • Output: Sum = 12, "Preorder: 5 3 1 4 7"
  • Explanation: Values 3, 4, 5 are in [2, 6], sum = 3 + 4 + 5 = 12.
  • Input: Tree = [5, left: [3, left: [1], right: [4]], right: [7]], Range = [8, 10]
  • Output: Sum = 0, "Preorder: 5 3 1 4 7"
  • Explanation: No values in [8, 10], sum = 0.
  • Input: Tree = [], Range = [1, 5]
  • Output: Sum = 0, "Empty"
  • Explanation: Empty tree, sum = 0.

Pseudocode

CLASS Node
    SET value to integer
    SET left to Node (null by default)
    SET right to Node (null by default)
ENDCLASS

FUNCTION rangeSum(root, low, high)
    IF root is null THEN
        RETURN 0
    ENDIF
    IF root.value < low THEN
        RETURN rangeSum(root.right, low, high)
    ENDIF
    IF root.value > high THEN
        RETURN rangeSum(root.left, low, high)
    ENDIF
    RETURN root.value + rangeSum(root.left, low, high) + rangeSum(root.right, low, high)
ENDFUNCTION

FUNCTION toString(root)
    IF root is null THEN
        RETURN "Empty"
    ENDIF
    CREATE result as new StringBuilder
    FUNCTION preorder(node)
        IF node is null THEN
            RETURN
        ENDIF
        APPEND node.value and " " to result
        CALL preorder(node.left)
        CALL preorder(node.right)
    ENDFUNCTION
    CALL preorder(root)
    RETURN "Preorder: " + result as string
ENDFUNCTION

FUNCTION main()
    SET testCases to array of (tree, low, high) pairs
    FOR each testCase in testCases
        PRINT test case details
        CALL rangeSum(testCase.root, testCase.low, testCase.high)
        PRINT sum and tree using toString
    ENDFOR
ENDFUNCTION

Algorithm Steps

  1. Reuse the Node class with: a. An integer value. b. left and right pointers to child nodes.
  2. Define rangeSum: a. If root is null, return 0. b. If root.value < low, skip left subtree, recurse on right. c. If root.value > high, skip right subtree, recurse on left. d. If root.value is in [low, high], include value and recurse on both subtrees.
  3. Define toString: a. If root is null, return "Empty". b. Perform preorder traversal, appending values to a string.
  4. In main, test with: a. A tree with values in the range. b. A tree with no values in the range. c. An empty tree. d. A range covering all values. e. A single-node tree.

Java Implementation

public class RangeSumQuery {
    // Node class for the binary search tree
    static class Node {
        int value;
        Node left, right;

        Node(int value) {
            this.value = value;
            this.left = null;
            this.right = null;
        }
    }

    // Computes the sum of values in the range [low, high]
    public int rangeSum(Node root, int low, int high) {
        if (root == null) {
            return 0;
        }
        if (root.value < low) {
            return rangeSum(root.right, low, high);
        }
        if (root.value > high) {
            return rangeSum(root.left, low, high);
        }
        return root.value + rangeSum(root.left, low, high) + rangeSum(root.right, low, high);
    }

    // Converts tree to string (preorder traversal)
    public String toString(Node root) {
        if (root == null) {
            return "Empty";
        }
        StringBuilder result = new StringBuilder();
        preorder(root, result);
        return "Preorder: " + result.toString().trim();
    }

    private void preorder(Node node, StringBuilder result) {
        if (node == null) {
            return;
        }
        result.append(node.value).append(" ");
        preorder(node.left, result);
        preorder(node.right, result);
    }

    // Helper class for test cases
    static class TestCase {
        Node root;
        int low, high;

        TestCase(int[] values, int[][] edges, int low, int high) {
            this.low = low;
            this.high = high;
            if (values.length == 0) {
                root = null;
                return;
            }
            Node[] nodes = new Node[values.length];
            for (int i = 0; i < values.length; i++) {
                nodes[i] = new Node(values[i]);
            }
            for (int[] edge : edges) {
                int parent = edge[0], child = edge[1];
                if (edge[2] == 0) {
                    nodes[parent].left = nodes[child];
                } else {
                    nodes[parent].right = nodes[child];
                }
            }
            root = nodes[0];
        }
    }

    // Main method to test range sum query
    public static void main(String[] args) {
        RangeSumQuery query = new RangeSumQuery();

        // Test cases
        TestCase[] testCases = {
            // Values in range: [5, left: [3, left: 1, right: 4], right: 7], range [2, 6]
            new TestCase(
                new int[]{5, 3, 1, 4, 7},
                new int[][]{{0, 1, 0}, {0, 4, 1}, {1, 2, 0}, {1, 3, 1}},
                2, 6
            ),
            // No values in range: [5, left: [3, left: 1, right: 4], right: 7], range [8, 10]
            new TestCase(
                new int[]{5, 3, 1, 4, 7},
                new int[][]{{0, 1, 0}, {0, 4, 1}, {1, 2, 0}, {1, 3, 1}},
                8, 10
            ),
            // Empty tree: [], range [1, 5]
            new TestCase(new int[]{}, new int[][]{}, 1, 5),
            // Range covers all: [5, left: [3, left: 1, right: 4], right: 7], range [0, 10]
            new TestCase(
                new int[]{5, 3, 1, 4, 7},
                new int[][]{{0, 1, 0}, {0, 4, 1}, {1, 2, 0}, {1, 3, 1}},
                0, 10
            ),
            // Single node: [10], range [5, 15]
            new TestCase(new int[]{10}, new int[][]{}, 5, 15)
        };

        // Run test cases
        for (int i = 0; i < testCases.length; i++) {
            System.out.println("Test case " + (i + 1) + ":");
            System.out.println("Tree: " + query.toString(testCases[i].root));
            System.out.println("Range: [" + testCases[i].low + ", " + testCases[i].high + "]");
            int sum = query.rangeSum(testCases[i].root, testCases[i].low, testCases[i].high);
            System.out.println("Sum: " + sum + "\n");
        }
    }
}

Output

Running the main method produces:

Test case 1:
Tree: Preorder: 5 3 1 4 7
Range: [2, 6]
Sum: 12

Test case 2:
Tree: Preorder: 5 3 1 4 7
Range: [8, 10]
Sum: 0

Test case 3:
Tree: Empty
Range: [1, 5]
Sum: 0

Test case 4:
Tree: Preorder: 5 3 1 4 7
Range: [0, 10]
Sum: 20

Test case 5:
Tree: Preorder: 10
Range: [5, 15]
Sum: 10

Explanation:

  • Test case 1: Values 3, 4, 5 are in [2, 6], sum = 3 + 4 + 5 = 12.
  • Test case 2: No values in [8, 10], sum = 0.
  • Test case 3: Empty tree, sum = 0.
  • Test case 4: All values (1, 3, 4, 5, 7) in [0, 10], sum = 1 + 3 + 4 + 5 + 7 = 20.
  • Test case 5: Single node 10 in [5, 15], sum = 10.

How It Works

  • Node: Stores an integer value and pointers to left and right children.
  • rangeSum:
    • Returns 0 for null nodes.
    • If root.value < low, skips left subtree, recurses on right.
    • If root.value > high, skips right subtree, recurses on left.
    • If root.value in [low, high], includes value and recurses on both subtrees.
  • toString: Performs preorder traversal, returns space-separated values or "Empty".
  • Example Trace (Test case 1):
    • Root=5: In [2, 6], sum = 5 + rangeSum(left, 2, 6) + rangeSum(right, 2, 6).
    • Left=3: In [2, 6], sum = 3 + rangeSum(left=1, 2, 6) + rangeSum(right=4, 2, 6).
    • Left=1: Not in [2, 6], skip left, sum = rangeSum(right=null, 2, 6) = 0.
    • Right=4: In [2, 6], sum = 4 + rangeSum(null, 2, 6) + rangeSum(null, 2, 6) = 4.
    • Right=7: > 6, skip right, sum = rangeSum(left=null, 2, 6) = 0.
    • Total: 5 + (3 + 0 + 4) + 0 = 12.
  • Main Method: Tests range with values, no values, empty tree, all values, and single node.

Complexity Analysis Table

OperationTime ComplexitySpace Complexity
rangeSumO(n) worst caseO(h)
toStringO(n)O(h)

Note:

  • n is the number of nodes in the tree.
  • h is the height of the tree (O(n) for skewed, O(log n) for balanced).
  • Time complexity: O(n) for rangeSum in worst case (all nodes in range); O(h) in best case (pruning skips subtrees).
  • Space complexity: O(h) for recursion stack in rangeSum and toString.
  • Worst case: O(n) time and O(n) space for skewed trees with all nodes in range.

✅ Tip: Leverage the BST property to prune branches outside the range, reducing unnecessary traversals. Use inorder traversal logic to ensure values are processed in sorted order.

⚠ Warning: Ensure the range is inclusive ([low, high]) and handle edge cases like empty trees or ranges outside the tree’s values to avoid incorrect sums.