Skip to content

938. Range Sum of BST 👍

  • Time: $O(n)$
  • Space: $O(h)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
 public:
  int rangeSumBST(TreeNode* root, int L, int R) {
    if (root == nullptr)
      return 0;
    if (root->val < L)
      return rangeSumBST(root->right, L, R);
    if (root->val > R)
      return rangeSumBST(root->left, L, R);
    return root->val + rangeSumBST(root->left, L, R) +
           rangeSumBST(root->right, L, R);
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution {
  public int rangeSumBST(TreeNode root, int L, int R) {
    if (root == null)
      return 0;
    if (root.val < L)
      return rangeSumBST(root.right, L, R);
    if (root.val > R)
      return rangeSumBST(root.left, L, R);
    return root.val + rangeSumBST(root.left, L, R) + rangeSumBST(root.right, L, R);
  }
}