How to get the Range Sum of Binary Search Tree using Java

Given the root node of a binary search tree, return the sum of values of all nodes with value between L and R (inclusive).

The binary search tree is guaranteed to have unique values.

Examples

Example1:

Input: root = [10,5,15,3,7,null,18], L = 7, R = 15
Output: 32

Example2:

Input: root = [10,5,15,3,7,13,18,1,null,6], L = 6, R = 10
Output: 23

Our solution in Java

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int rangeSumBST(TreeNode root, int L, int R) {
        //output variable
        int output = 0;
        
        // Create a stack
        Stack<TreeNode> stack = new Stack();
        // Add the root node
        stack.push(root);
        
        // loop through each element 
        while (!stack.isEmpty()) {
            
            // remove last item from stack
            TreeNode node = stack.pop();
            // if the node exists
            if (node != null) {
                
                // incrememnt output counts
                if (L <= node.val && node.val <= R)
                    output += node.val;
                
                // push if left
                if (L < node.val)
                    stack.push(node.left);
                
                // push if right
                if (node.val < R)
                    stack.push(node.right);
            }
        }
        
        // return our count
        return output;
    }
}
0 0 vote
Article Rating
Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments