The problem:

Find a formula for the total number of calls occurring during the insertion of n elements into an initially empty set. Assume that the insertion process fills up the binary search tree level-by-level. Leave your answer in the form of a sum.

code for INSERT function:

procedure INSERT(x: elementtype; var A: SET); 
    if A = nil then begin
       A -> .element := x; 
       A ->.leftchild := nil; 
       A ->.rightchild := nil;
    else if x < A ->.element then
        INSERT(x, A->.leftchild);
    else if x > A ->.element then 
        INSERT(x, A ->.rightchild);

The main confusion for me here is with leaving my answer in the form of a sum. I'm not all that great at sums (haven't taken Calc 2 yet), so I don't really know how to set them up or extract information from them all that well. Any help here would be greatly appreciated.

For clarity: This is a review problem where the answer is:

Let $2^k \leq n \leq 2^{k+1}$. Then $k = \log n$ and the number of calls equals,

$$ \sum_{i = 0}^{k - 1} (i + 1)2^i + (k + 1)(n - 2^k + 1) $$

I'd like to know the process behind getting this answer. Thank you.


1 Answer 1


The key observation here is that the input is assumed to be such that all insertions fill level 0 (the root level), then completely fill level 1, then completely fill level 2, and so on.

In filling level $i$ we will have constructed $2^i$ new nodes, each of which will require $i+1$ calls to INSERT, so the total cost to fill level $i$ will be $(i+1)2^i$. Thus, the cost to fill levels $0, 1,\dotsc, k-1$ will be $$ \sum_{i=0}^{k-1}(i+1)2^i $$ Now let's say we're finishing by filling level $k$ partially or fully. We're then inserting elements $n=2^k,2^k+1,2^k+2, \dotsc, 2^{k+1}-1$. Each of those will cost $k+1$ calls to INSERT, so for $n$ elements we will have used $n-2^k+1$ insertions, each of cost $k+1$ for a total of $(k+1)(n-2^k+1)$ calls. That must be added to the cost of filling the upper rows, so you get a total cost of inserting $n$ elements level-by-level equal to $$ \left(\sum_{i=0}^{k-1}(i+1)2^i\right) + (k+1)(n-2^k+1) $$

  • $\begingroup$ Thank you very much! This is the explanation I needed. Learned a bit more about sums from your answer as well :D $\endgroup$ Mar 1, 2016 at 16:45
  • $\begingroup$ Am I right in assuming that we need i + 1 calls because, if we insert i nodes, then we need to make 1 more call to insert the root? $\endgroup$ Mar 1, 2016 at 17:27
  • $\begingroup$ @MatthewFreihofer. Exactly. $\endgroup$ Mar 1, 2016 at 17:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.