Binary Search Trees: Given a BST and a range, return the range sum of that BST

Problem Statement:

Given a BST and a range [low, high], return the range sum of that BST

Example:

Input:

    /*
     *           10
     *         /    \
     *        8      12
     *       / \    /  \
     *      2   9  11   14
     */

low = 8, high = 12

Output: 50

Explanation: 8 + 9 + 10 + 11 + 12 = 50

Solution Explanation:

We can solve the problem by doing DFS.

For each node, we will check if the data lies in between left and right.

If it lies inside, then add it to the sum.

Time Complexity: O(n)
Space Complexity: O(h) h is the height of the tree

Code Solution

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;

class Tree_Node 
{
public:
	int data;
	Tree_Node* left;
	Tree_Node* right;

	Tree_Node(int x) 
	{
		data = x;
		left = nullptr;
		right = nullptr;
	}
};


int solution(Tree_Node* root, int low, int high) 
{
    if (!root) 
    {
        return 0;
    }
    
    int currentVal = (root->data >= low && root->data <= high) ? root->data : 0;
    
    int leftSum = solution(root->left, low, high);
    int rightSum = solution(root->right, low, high);
    
    return currentVal + leftSum + rightSum;
}


int main()
{

    /*
     *           10
     *         /    \
     *        8      12
     *       / \    /  \
     *      2   9  11   14
     */
    Tree_Node* root = new Tree_Node(10);
    root->left = new Tree_Node(8);
    root->right = new Tree_Node(12);
    root->left->left = new Tree_Node(2);
    root->left->right = new Tree_Node(9);
    root->right->left = new Tree_Node(11);
    root->right->right = new Tree_Node(14);

    int low = 8, high = 12;

    cout <<solution(root, low, high);

    return 0;
}

Output

50