/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int rangeSumBST(const TreeNode* root, int L, int R) {
        return L > R ? 0
            : L == R ? sU(root, L)
            : sLR(root, L, R);
    }

    int sLR(const TreeNode* n, int L, int R) {
        return n == nullptr ? 0
            : n->val >  R ? sLR(n->left, L, R)
            : n->val == R ? n->val + sL(n->left, L)
            : n->val <  L ? sLR(n->right, L, R)
            : n->val == L ? n->val + sR(n->right, R)
            : n->val + sLR(n->left, L, R) + sLR(n->right, L, R);
    }

    int sR(const TreeNode* n, int R) {
        return n == nullptr ? 0
            : n->val >  R ? sR(n->left, R)
            : n->val == R ? n->val + s(n->left)
            : n->val + sR(n->left, R) + sR(n->right, R);
    }

    int sL(const TreeNode* n, int L) {
        return n == nullptr ? 0
            : n->val <  L ? sL(n->right, L)
            : n->val == L ? n->val + s(n->right)
            : n->val + sL(n->left, L) + sL(n->right, L);
    }

    int s(const TreeNode* n) {
        return n == nullptr ? 0 : n->val + s(n->left)  + s(n->right);
    }

    int sU(const TreeNode* n, int U) {
        return n == nullptr ? 0
            : n->val < U ? sU(n->right, U)
            : n->val > U ? sU(n->left, U)
            : U;
    }
};