int getSum(node *root, int L, int H)
{
// Base Case
if (root == NULL)
return 0;
if (root->key < L)
return getSum(root->right, L, H);
if (root->key > H)
return getSum(root->left, L, H)
if (root->key >= L && root->key <=H)
return getSum(root->left, L, H) + root->key +
getSum(root->right, L, H);
}
it will be O(logn +m)
it can go max of logn depth to find nodes in range and function calls for nodes in range ie m
Note that the code first traverses across height to find the node which lies in range. Once such a node is found, it recurs for left and right children. Two recursive calls are made only if the node is in range. So for every node that is in range, we make at most one extra call (here extra call means calling for a node that is not in range).
source:http://geeksquiz.com/gate-gate-cs-2014-set-3-question-49/