I need to prove the following statement using induction on the number of nodes in the tree:The sum of heights of a complete binary tree is $\theta(n)$.Note: I've tried proving this using mathematical sums. I did manage to show that the sum of heights (lets call it $sum(n)$) is in fact $sum(n)c_1n$ for some $c_1$. But, I couldn't show the lower bound ($sum(n)c_2n$ for some $c_2$).The base case is a complete binary tree, with 3 nodes in the height of 1.The assumption is that for a complete binary tree $T$ with $n$ nodes $sum\in\theta(n)$I got stuck when i got to the phase of the step. My intuition is to add to the tree another depth of leaves and to prove for the new tree. Can someone explain how to complete this step?
Sum of heights in a complete binary tree (induction)
binary trees;induction