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

1
2

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

1
2

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

/**
 * 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;
    }
}