0
$\begingroup$

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.

Improve this question
$\endgroup$
7
  • 1
    $\begingroup$ 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? $\endgroup$
    – Nathaniel
    Dec 21, 2021 at 5:02
  • 2
    $\begingroup$ 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. $\endgroup$
    – D.W. ♦
    Dec 21, 2021 at 5:05
  • $\begingroup$ @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. $\endgroup$
    – user126100
    Dec 21, 2021 at 6:22
  • $\begingroup$ 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. $\endgroup$
    – Nathaniel
    Dec 21, 2021 at 6:38
  • 2
    $\begingroup$ 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. $\endgroup$
    – Yuval Filmus
    Dec 21, 2021 at 7:28

1 Answer 1

Reset to default
1
$\begingroup$

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

Improve this answer
$\endgroup$
3
  • $\begingroup$ @user126100, you accepted the answer without upvoting it. Can you explain the reason why you did not think this answer was helpful? $\endgroup$
    – John L.
    Dec 23, 2021 at 11:56
  • $\begingroup$ @John L. when I click, it says you need 15 reputation to upvote posts. $\endgroup$
    – user126100
    Oct 10, 2022 at 10:39
  • $\begingroup$ @user126100 Your account here is an unregistered account. Would you mind registering your account? Once you are a registered user on this site, you will be able to vote since you have 181>=15 reputation. $\endgroup$
    – John L.
    Oct 10, 2022 at 12:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.