LeetCode Solutions

938. Range Sum of BST

Time: $O(n)$

Space: $O(h)$

			

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);
  }
};
			

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);
  }
}