Range Sum of BST

class Solution {
    public int sumRangeBST(TreeNode node, int L, int H) {
        int total = 0;
        Stack<TreeNode> nodes = new Stack();
        nodes.push(node);
        while (!nodes.isEmpty()) {
            TreeNode current = nodes.pop();
            if (current != null) {
                if (L <= current.val && current.val <= H)
                    total += current.val;
                if (L < current.val)
                    nodes.push(current.left);
                if (current.val < H)
                    nodes.push(current.right);
            }
        }
        return total;
    }
}

This Java solution uses a non-recursive approach to calculate the sum of values within a specified range [L, H] in a Binary Search Tree (BST). The method, sumRangeBST(TreeNode node, int L, int H), utilizes a Stack<TreeNode> to iterate through the tree without recursion.

The algorithm works as follows:

1. Initialize total to store the sum of nodes' values that fall within the range.
2. Create and initialize a Stack<TreeNode> and push the root node onto the stack.
3. Use a while loop to process nodes until the stack is empty:
   • Pop the top node from the stack.
   • If the node is not null, check if node's value is within the [L, H]. If so, add the value to total.
   • Depending on the node's value, decide whether to traverse left or right:
     • If node's value is greater than L, push the left child to the stack.
     • If node's value is less than H, push the right child to the stack.

With this implementation, you efficiently explore only the relevant parts of the BST, avoiding unnecessary traversal and achieving optimized performance especially for larger trees. This method ensures a stack-based DFS execution where only relevant subtrees are explored based on the comparison with limits L and H. It is a robust solution handling the structure and constraints of BST efficiently.

class Solution:
    def sumBST(self, node_root: Optional[TreeNode], min_val: int, max_val: int) -> int:
        total = 0
        nodes = [node_root]
        while nodes:
            current = nodes.pop()
            if current:
                if min_val <= current.val <= max_val:
                    total += current.val
                if min_val < current.val:
                    nodes.append(current.left)
                if current.val < max_val:
                    nodes.append(current.right)
        return total

The solution presented outlines a method to calculate the sum of values of all nodes in a binary search tree (BST) that fall within a given range, defined by min_val and max_val. This Python function named sumBST uses a non-recursive, iterative approach to traverse the BST while accumulating the sum of node values that respect the range criteria.

Here's a breakdown of the procedure:

1. Initialize a variable total to zero to store the cumulative sum of node values that fall within the specified range.
2. Create a list nodes initially consisting of the node_root, which acts as a stack to manage the nodes yet to be processed.
3. Utilize a while loop that continues as long as there are nodes in the nodes list:
   • Extract the latest node from the stack using pop().
   • Check if the node exists:
     • If the node's value falls within min_val and max_val, add its value to total.
     • Add the node's children to the stack based on whether their values could potentially fall within the given range:
       • The left child is added if min_val is less than the current node's value.
       • The right child is added if the current node's value is less than max_val.
4. Return the accumulated value in total upon completion of the loop.

This function effectively balances the traversal without the need for recursion, ensuring efficient handling of large data structures by using an iterative approach with a stack. Its check before traversal of child nodes also minimizes unnecessary operations, promoting faster computation by focusing only on relevant portions of the BST.