Binary Search Trees (BSTs) are a fundamental data structure in computer science, known for their efficient search and retrieval operations. In this blog, we’ll delve into a Java solution for calculating the sum of values within a specified range in a BST. The provided code snippet showcases a recursive approach to achieve this task.

Understanding the Problem

The task at hand is to calculate the sum of all node values within a given range [low, high] in a Binary Search Tree. The provided Java class Solution contains a method rangeSumBST that initiates the process, calling the recursive function visit on the root node.

Let’s break down the key components of the solution:

class Solution {
    public int rangeSumBST(TreeNode root, int low, int high) {
        return visit(root, low, high);
    }

    public int visit(TreeNode node, int low, int high) {
        // Base condition
        if (node == null) {
            return 0;
        }

        if (node.val >= low && node.val <= high) {
            return node.val + visit(node.left, low, high) + visit(node.right, low, high);
        }

        return visit(node.left, low, high) + visit(node.right, low, high);
    }
}

Exploring the Code

1. Method rangeSumBST

The rangeSumBST method serves as the entry point for calculating the sum within the specified range. It takes three parameters:

• root: The root node of the Binary Search Tree.
• low: The lower bound of the range.
• high: The upper bound of the range.

The method then calls the visit function, passing these parameters.

2. Method visit

The visit method is a recursive function that traverses the BST nodes and accumulates the sum of values within the specified range. It follows these steps:

• Base Condition: If the current node is null, the function returns 0.
• If the value of the current node is within the specified range [low, high], the node’s value is added to the sum.
• The function then recursively calls itself on the left and right children of the current node.
• The sum of values within the range is calculated and returned.

Problem Url: https://leetcode.com/problems/range-sum-of-bst/description/

Conclusion

The provided Java solution elegantly solves the problem of calculating the sum of values within a specified range in a Binary Search Tree. Understanding recursive traversal and leveraging the properties of BSTs are essential skills for mastering such algorithms. Feel free to integrate this solution into your projects or use it as a foundation for further exploration into binary tree operations in Java. Happy coding!