/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    private List<Integer> values;
    private int[] prefixSum;
    
    public int rangeSumBST(TreeNode root, int low, int high) {
        values = new ArrayList<>();
        inOrder(root);
        
        if (values.isEmpty()) return 0;
        
        prefixSum = new int[values.size()];
        int sum = 0;
        for (int i = 0; i < prefixSum.length; i++) {
            prefixSum[i] = sum = sum + values.get(i);
        }

        int left = Collections.binarySearch(values, low);
        int right = Collections.binarySearch(values, high);
        
        // Handle cases where exact values aren't found
        if (left < 0) left = -(left + 1);    // Insertion point
        if (right < 0) right = -(right + 1) - 1; // Last index before insertion point
        
        // if (left >= values.size() || right < 0) return 0;
        
        // Adjust for inclusive range
        if (left > 0) {
            return prefixSum[right] - prefixSum[left - 1];
        } else {
            return prefixSum[right];
        }
    }
    
    private void inOrder(TreeNode node) {
        if (node == null) return;
        inOrder(node.left);
        values.add(node.val);
        inOrder(node.right);
    }
}