I have to show that a binary tree with $n$ nodes has at least $(n-1)/2$ weight-balanced nodes and at most $n-1$ weight-balanced nodes. Here a node is weight-balanced if its siblings satisfy $\operatorname{weight}(u) \leq 2\operatorname{weight}(v)$.

So we get at least $(n-1)/2$ (where $n$ is positive and odd) if the one sibling satisfies $\operatorname{weight}(u)≤2\operatorname{weight}(v)$ and the other one doesn't (i.e. half of them when we disregard the root node).

And we get at most $n-1$ if both siblings satisfy $\operatorname{weight}(u)≤2\operatorname{weight}(v)$, so all nodes are weight-balanced except for the root node.

But how can I formally show that?

  • $\begingroup$ a node is weight balanced if for siblings $u$ and $v$ $weight(v) \le 2 weight(u) \le 4 weight(v)$ depends on definition: make it one. $\endgroup$ – greybeard Nov 21 '20 at 14:13
  • $\begingroup$ I don't understand the definition of weight-balanced. I'm afraid it might be a linguistic issue. $\endgroup$ – Yuval Filmus Nov 21 '20 at 22:57

Your Answer

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

Browse other questions tagged or ask your own question.