# Deriving the average depth for a randomly generated binary search tree

If $$D(n)$$ is the internal path length (sum of the depths of all nodes) for some tree $$T$$ with $$n$$ nodes then we have the following recurrence relation: $$D(n)=D(i)+D(n-i-1)+N-1$$ where I simply taken an arbitrary tree with a left subtree containing $$i$$ nodes and the right subtree containing $$n-i-1$$ nodes.

Correct me if I'm misunderstanding this, but since these left and right subtrees can be anything (where $$i=0,1,2,...,n-1$$) then the average of $$D$$ is given by $$\langle D \rangle=\dfrac{1}{n}\left(2\sum_{i=0}^{n-1}D(i)+\sum_{i=0}^{n-1}(n-1)\right)$$ where I divided by $$n$$ since there are $$n$$ different left/right-subtree possibilities. What I don't understand is that online sources and my textbook equates this to $$D$$ itself. In other words, I don't quite understand why we're allowed to set $$\langle D(n) \rangle = D(n)$$.

Ignoring that, I continued on and I'm also running into the problem where my book is writing $$D(n) =\dfrac{1}{n}\left(2\sum_{i=0}^{n-1}D(i)+(n-1)\right)$$ and seems to be ignoring the sum altogether. The reason why I say this is because later the book claims that $$nD(n) =2\sum_{i=0}^{n-1}D(i)+n(n-1)$$ This doesn't make any sense to me since I had a $$\sum_{i=0}^{n-1}(n-1)\in O(n^2)$$ term in my expression so multiplying by another $$n$$ should be give me something like $$nD(n) =2\sum_{i=0}^{n-1}D(i)+O(n^3)$$ instead. I feel like I'm missing something obvious but I can't quite figure it out. Any ideas?

Suppose that $$T$$ is a random tree on $$n$$ vertices, according to the distribution you consider. Let $$T_L,T_R$$ be its two subtrees, and let their size be $$N_L,N_R$$. Let $$P$$ be the total path length of $$T$$. Let $$P_L(i)$$ be the total path length of $$T_L$$ if $$N_L=i$$, and zero otherwise, and define $$P_R(i)$$ similarly. We have $$P = \sum_{i=0}^{n-1} (P_L(i) + P_R(n-1-i)) + n-1.$$ According to linearity expectation, we have $$\mathbb{E}[P] = \sum_{i=0}^{n-1} (\mathbb{E}[P_L(i)] + \mathbb{E}[P_R(n-1-i)]) + n-1.$$ By definition, $$\mathbb{E}[P] = D(n)$$, where $$D(n)$$ is the expected internal path length of a random tree on $$n$$ vertices.
According to your probability distribution, the probability that $$N_L=i$$ is $$1/n$$. When that happens, $$T_L$$ is just a random tree on $$i$$ vertices. Therefore $$\mathbb{E}[P_L(i)] = \Pr[N_L=i] \mathbb{E}[P_L(i)|N_L=i] + \Pr[N_L\neq i] \mathbb{E}[P_L(i)|N_L\neq i] = \\ \frac{1}{n} \cdot D(i) + \left(1-\frac{1}{n}\right) \cdot 0 = \frac{D(i)}{n}.$$ Therefore we obtain the recurrence $$D(n) = \frac{1}{n} \sum_{i=0}^{n-1} (D(i) + D(n-1-i)) + n-1 = \frac{2}{n} \sum_{i=0}^{n-1} D(i) + n-1.$$ Equivalently, $$nD(n) = 2\sum_{i=0}^{n-1} D(i) + n(n-1).$$ The initial condition is $$D(0) = 0$$.
We can solve this recurrence using generating functions. Let $$P(x) = \sum_{n=0}^\infty D(n) x^n$$. First, $$P'(n) = \sum_{n=1}^\infty nD(n) x^{n-1}.$$ Second, $$\frac{P(n)}{1-x} = \sum_{n=0}^\infty [D(0) + \cdots + D(n)] x^n.$$ Third, $$\sum_{n=0}^\infty n(n-1) x^{n-2} = \frac{d^2}{dx^2} \frac{1}{1-x} = \frac{2}{(1-x)^3}.$$ Putting everything together, we obtain $$P'(x) = \sum_{n=1}^\infty nD(n) x^{n-1} = 2\sum_{n=1}^\infty (D(0) + \cdots + D(n-1)) x^{n-1} + \sum_{n=1}^\infty n(n-1) x^{n-1} = \\ \frac{2P(x)}{1-x} + \frac{2x}{(1-x)^3}.$$ The solution to this ODE is $$P(x) = \frac{-2\log (1-x)-2x}{(1-x)^2} = \frac{1}{(1-x)^2} \sum_{n=2}^\infty \frac{2}{n} x^n,$$ which implies that $$D(n) = 2\sum_{m=2}^n \frac{n-m+1}{m} = 2(n+1)(H_n-1)-2(n-1) = 2(n+1)H_n-4n.$$ Since $$H_n = \ln n + \gamma + 1/2n + O(1/n^2)$$, we deduce that $$D(n) = 2(n+1)(\ln n + \gamma + 1/2n + O(1/n^2)) - 4n = \\ 2n\ln n + 2\ln n + (2\gamma-4) n + 2\gamma + 1 + O(1/n).$$
You don't need to multiply by $$n$$ in the last but one expression, because the right hand side of the D(n) expression has the factor $$\frac{1}{n}$$.
So you only have to explain the $$\mathcal{O}(n^2)$$ versus $$\mathcal{O}(n)$$ terms; not the $$\mathcal{O}(n^3)$$ versus $$\mathcal{O}(n)$$ terms.
Also, I have a doubt whether one can take $$i$$ to be really arbitrary (e.g. 0) in the first expression. When $$i=0$$ it means the left sub-tree is empty, so the initial is not really a binary tree.