Range Sum Of BST | LeetCode

Range Sum of BST Link

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.

Example 1:

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

Output: 32

Example 2:

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

Output: 23

Note:

• The number of nodes in the tree is at most 10000.
• The final answer is guaranteed to be less than 2^31.

Solution:

We will implement the solution using depth-first search technique. Here we use a recursive approach to implement DFS. You can use iterative approach as well. If recursively travel though the tree if any value falls outside the range, for example if value is less than L, then we can comclude that our answer is there somewhere in right branch of the tree.

Implementation:

Java:

class Solution {
    int ans;
    public int rangeSumBST(TreeNode root, int L, int R) {
        ans = 0;
        dfs(root, L, R);
        return ans;
    }

    public void dfs(TreeNode node, int L, int R) {
        if (node != null) {
            if (L <= node.val && node.val <= R)
                ans += node.val;
            if (L < node.val)
                dfs(node.left, L, R);
            if (node.val < R)
                dfs(node.right, L, R);
        }
    }
}

Complexity Analysis:

• Time Complexity: O(n).
• Space Complexity: O(H). where H is the height of the tree.