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.
Total number of calls during insertion into binary tree
trees;binary trees;sets;binary search