Range Sum of BST

Problem

Given the root node of a binary search tree and two integers low and high, return the sum of values of all nodes with a value in the inclusive range [low, high].

Constraints

• The number of nodes in the tree is in the range [1, 2 * 104].
• 1 <= Node.val <= 105
• 1 <= low <= high <= 105
• All Node.val are unique.

Solution

The problem Range Sum of BST can be solved using a depth-first search to find all nodes that are within the given range.

Implementation

static const int fast_io = []()
{
    std::ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    return 0;
}();

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution
{
  public:
    void inorder(TreeNode *root, int low, int high, int &res)
    {
        if (root == NULL)
            return;

        if (low <= root->val)
            inorder(root->left, low, high, res);
        if (low <= root->val && root->val <= high)
            res += root->val;
        if (root->val <= high)
            inorder(root->right, low, high, res);
    }

    int rangeSumBST(TreeNode *root, int low, int high)
    {
        int ret = 0;
        inorder(root, low, high, ret);
        return ret;
    }
};