hi, let Avik connect you.


** You can give your thought about this content and request modifications if needed from Ask For Modifications page. Thank You.

** You can check all the posts on the Posts page.

** More about me in the About Me section.

Range Sum of BST


  • Approach:

  1. Traversed through all the nodes in the given Tree using Inorder fashion.

  2. Checked whether the root_node's value is greater than low and lesser than high or not.

  3. If satisfy the condition then added the root node's value with the sum of the left sub-tree and the right sub-tree.

  4. Return the sum.


  • Time and Space Complexity:

    • Time complexity: O(n)

    • Space complexity: O(1) + Auxilary Stack.


Code [C++]

/**

* 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:

int rangeSumBST(TreeNode* root, int low, int high) {

if(!root) return 0;

int sum = rangeSumBST(root->left, low, high);

sum += (root->val >= low && root->val <= high) ? root->val : 0;

sum += rangeSumBST(root->right, low, high);

return sum;

}

};