Total number of calls during insertion into binary tree

Question

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); 
begin
    if A = nil then begin
       A -> .element := x; 
       A ->.leftchild := nil; 
       A ->.rightchild := nil;
    end;
    else if x < A ->.element then
        INSERT(x, A->.leftchild);
    else if x > A ->.element then 
        INSERT(x, A ->.rightchild);
    end;
end;

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.

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) $$