Time limit: 5000ms
Memory limit: 256mb

Description:
In this exercise, you are required to fulfill the following two tasks.

1. Construct a binary search tree(BST).
Initially, the BST is empty. Then given a sequence of distinct integers, you need to insert them into the BST one by one. Lecture notes show more details on insertion.

2. Given a range query of start and end, return the sum of the values of all nodes whose values are within the inclusive range [start, end] and whose values are greater than the root value.

The main function has been provided. You need to complete three functions.

Node* createNode(int data);

Node* insertNode(Node* root, int data);

int rangeSumWithLimit(Node* root, Node* cur, int start, int end);

Sample Input 1:
5
10 20 30 50 40
20 40

Sample Output 1:
Input the number of integers:
Input these integers:
Input start and end:
Range Sum:
90

Sample Input 2:
11
2 1 4 10 3 5 7 8 9 6 0
2 10

Sample Output 2:
Input the number of integers:
Input these integers:
Input start and end:
Range Sum:
52

Sample Input 3:
5
3 1 2 4 5
2 4

Sample Output 3:
Input the number of integers:
Input these integers:
Input start and end:
Range Sum:
4


Code Template:

#include <stdio.h>
#include <stdlib.h>

// Define the structure for BST node
typedef struct Node {
    int data;
    struct Node* left;
    struct Node* right;
} Node;

// Function to create a new node
Node* createNode(int data) {
    /*
        Fill in your code here...
    */
}

// Function to insert a node in the BST
Node* insertNode(Node* root, int data) {
    if (root == NULL) {
        return createNode(data);
    }

    /*
        Fill in your code here...
    */

    return root;
}

int rangeSumWithLimit(Node* root, Node* cur, int start, int end) {
    int range_sum = 0;
    /*
        Fill in your code here...
        Calculate the range sum between any two nodes.
    */
    return range_sum;
}

int main()
{
    int n, key;
    Node* root = NULL;
    printf("Input the number of integers:\n");
    scanf("%d",&n);
    printf("Input these integers:\n");
    for(int i=0; i<n; i++)
    {
        scanf("%d", &key);
        root = insertNode(root, key);
    }
    int start, end;
    printf("Input start and end:\n");
    scanf("%d", &start);
    scanf("%d", &end);
    // Find the range sum between any two different nodes, whose data larger than root's data
    int range_sum = rangeSumWithLimit(root, root, start, end);
    printf("Range Sum:\n%d", range_sum);

    return 0;
}