Deriving the average depth for a randomly generated binary search tree

Question

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?

Answer 1

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

Answer 2

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.