# Total number of calls during insertion into binary tree

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.

## 1 Answer

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

• Thank you very much! This is the explanation I needed. Learned a bit more about sums from your answer as well :D – Matthew Freihofer Mar 1 '16 at 16:45
• 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? – Matthew Freihofer Mar 1 '16 at 17:27
• @MatthewFreihofer. Exactly. – Rick Decker Mar 1 '16 at 17:49