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?

New contributor
parama is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
  • $\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 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 at 22:57

Your Answer

parama is a new contributor. Be nice, and check out our Code of Conduct.

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.