# What's the sum of heights of a random binary search tree

What's the sum of heights of a random binary search tree?

By a random binary search tree, I mean the usual definition: you have $$n$$ keys to be inserted, and all Permutations are equally likely.

The sum of heights is the sum of the heights of each node. similar to Sum of heights in a complete binary tree (induction)

My attempt: I know that a random binary tree has height $$O(\log n)$$, so $$h = K \log n$$ and the sum is bounded from above by the sum of heights of a perfectly balanced binary tree of height $$k\log n$$. which is $$2^{k\log n} -1 = n^k - 1$$. This leads me nowhere.

• The question is very vague: are you considering the heights of each node of a single BST? What does "random" mean? Is it an uniform distribution? Over which set of binary trees? Does the fact that it is a BST matter? Dec 21, 2021 at 5:02
• Please make sure that you include the question in the body of your post. I suggest that you specify the distribution on trees you have in mind. What do you mean by sum of heights? Sum over what? All nodes? Leaves? Something else? Please edit your question to improve it.
– D.W.
Dec 21, 2021 at 5:05
• @Nathaniel I edited the question. feel free to further edit it to your liking. But to to be honest this is absurd. I mean sum of heights means the sum over all heights of nodes, it's standard terminology. and by random, of course, I mean uniform distribution. Why would I mean anything else and not specify it. "Does the fact that it is a BST matter?" yes, the height would be O(sqrt(n)) otherwise. Dec 21, 2021 at 6:22
• Over the set $\{1, 2,3\}$, there are exactly 5 different BST. However, there are 6 permutations of the 3 keys. I hope that helps you to understand that there is no "standard" or "obvious" random distribution. Dec 21, 2021 at 6:38
• There are several common distributions over random binary trees. We can't read your mind. If you want people here to help you, you need to be more courteous. We don't work for you. Dec 21, 2021 at 7:28

According to Lemma 7.1 in these notes, if you construct a random BST on $$\{0,\ldots,n-1\}$$, then the expected depth of $$x \in \{0,\ldots,n-1\}$$ is $$H_{x+1} + H_{n-x} - 2$$, where $$H_m$$ is the $$m$$'th harmonic number. Summing over all $$x$$, the expected sum of depths is $$\sum_{x=0}^{n-1} (H_{x+1} + H_{n-x} - 2) = 2 \sum_{i=1}^n (H_i - 1) = 2 \sum_{i=1}^n \sum_{j=2}^i \frac{1}{j} = \\2\sum_{j=2}^n \frac{n-j+1}{j} = 2(n+1)(H_n - 1) - 2(n-1),$$ which is $$2n\ln n - O(n)$$.