# Number of weight-balanced nodes in binary tree

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?

• 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. – greybeard Nov 21 '20 at 14:13
• I don't understand the definition of weight-balanced. I'm afraid it might be a linguistic issue. – Yuval Filmus Nov 21 '20 at 22:57