Assume a proper and complete binary tree $T$ with $n>1$ nodes. Let $E(T)$ represent the sum of the depths of all external nodes in $T$, and $I(T)$ represent the sum of the depths of all internal nodes in $T$. Prove that:

$E(T) = O(n⋅\log n)$

To prove this that it is equal to $E(T)$, do I just go plug in numbers till I get the exact $E(T)$ given? I can't figure this out, can someone help?

  • $\begingroup$ You are not given an exact value for $E(T)$, only an estimate; in fact, only an upper bound. One way of proving this is calculating $E(T)$ exactly and then proving that the resulting expression is $O(n\log n)$. $\endgroup$ – Yuval Filmus Mar 28 '17 at 13:47
  • 1
    $\begingroup$ This appears to be copied word-for-word from a homework assignment in York University's EECS 2011, Assignment 2, Question 1, due March 28. Make sure to properly credit your sources in the question. You might find this page helpful for suggesting how to make use of this site to help you learn course material. $\endgroup$ – D.W. Mar 28 '17 at 21:25
  • $\begingroup$ Separately, some friendly advice: If you are part of the class, I suggest you check with your instructor about the class collaboration policy and check whether this use of the Internet is permitted. If you're not part of the class and you ran across the problem from the class's web site, we still expect you to provide attribution, and it might be for the best to wait until after the homework is due. $\endgroup$ – D.W. Mar 28 '17 at 21:27

Let $T$ be a complete binary tree of height $h$.

The number of nodes in the last level (external nodes) as a function of the height is $2^h$

The number of nodes in the tree as a function of the height is $2^{h+1}-1$.

Now you just need to compute $E(T)$ and prove that (a) holds.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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