CODEWITHSUNDEEP
algorithmsearch
Ujjwal Saini
Ujjwal Saini

Reputation: 17

time taken to sum up all the numbers in binary search tree that lie between two numbers

Suppose we have a balanced binary search tree T holding n numbers. We are given two numbers L and H and wish to sum up all the numbers in T that lie between L and H. Suppose there are m such numbers in T.Can someone explain how to calculate the absolute value of the time taken to compute the sum..?

Upvotes: 0

Views: 713

Answers (1)

chiastic-security
chiastic-security

Reputation: 20520

I'll leave you to work out the full details, but here's a start. The algorithm will go:

  1. Find the smallest number in the tree that's greater than L. You can do that in log time.
  2. Walk the tree, each time moving to the next largest, and adding it to a running total.
  3. Stop when you reach a number that's at least H.

I've assumed that "lie between" means "strictly between", but you might want weak inequalities in steps 1 and 3.

Upvotes: 2

Related Questions