Sum of Nodes in BST Range

JavaView on GFG

Time: O(n)

Space: O(h)

Intuition

Sum of all BST node values in range [low, high]. Range sum query on BST.

Algorithm

1DFS: if node.val < low: go right. If node.val > high: go left. Else: sum += node.val + both subtrees.

Common Pitfalls

•Same as LC 938. Use BST property to prune. O(n) worst, O(log n + k) average where k = nodes in range.

Sum of Nodes in BST Range.java

Java

// Approach: BST in-order traversal skipping branches outside [l, r]. Accumulate values in range.
// Time: O(n) Space: O(h)
import java.util.*;

class Node {
    int data;
    Node left, right;

    Node(int val) {
        data = val;
        left = right = null;
    }
}

class Solution {

    ArrayList<Integer> ob = new ArrayList<Integer>();
    int length = 0;

    public int nodeSum(Node root, int l, int r) {
        traversal(root);
        int sum = 0;
        for (int i = 0; i < length; i++) {
            if (ob.get(i) >= l && ob.get(i) <= r)
                sum = sum + ob.get(i);
        }
        return sum;
    }

    void traversal(Node root) {
        if (root == null)
            return;
        traversal(root.left);
        ob.add(root.data);
        length++;
        traversal(root.right);
    }
}

Was this solution helpful?