I'm trying to prove the following:
Given a binary tree $\,T\,$ if every subtree is of size $2^k-1\;$ for some $\;k\in\mathbb N$, then $\,T\,$ is balanced.
I've tried to disprove this but then it seemed to me like that condition imposes not only a balanced tree but also a perfect tree . I tried using induction on the height $h$:
and I am having trouble with the step part , Assuming that
for every tree $\,T'\,$ of height $\,n<h\,$ if every subtree is of size $2^k-1\;$ for some $\;k\in\mathbb N$, then $\,T'\,$ is balanced.
I now take a tree of height h, in which all subtrees have $2^k-1\,$ nodes for some $\;k\in\mathbb N$.
I now want to remove a node from the $\text{h th level} $ which must exist to get a tree of size $\,h-1$ and use the hypothesis to get a tree that satisfies the property therefore it is balanced and after adding the removed node back it's still balanced.
Any ideas? is this statement even true ? or is there a counterexample? Thanks in advance!
You can prove a stronger statement that the tree is a perfect binary tree, hence it is balanced in particular.
The entire tree is a subtree of itself; assume it has $2^p - 1$ nodes. Let also the left subtree have $2^k-1$ and the right one have $2^m-1$ nodes. Here $m, k, p \in \mathbb{N}$. Summing the nodes of left and right subtrees and adding $1$ for the root node we get the number of nodes in the entire tree, thus $$ 1 + 2^k - 1 + 2^m - 1 = 2^p - 1, $$ which is equivalent to $2^k + 2^m = 2^p$. Assume that $1\leq k\leq m < p$, hence dividing both sides of the last equation by $2^k$ we get $1 + 2^{m - k} = 2^{p - k} $. Since $1$ is not divisible by $2$ it follows that $m = k $ and hence $p = m + 1$. Summing up we get that the left and right subtrees have equal number of nodes. Applying induction of each of the left and right subtree we conclude that the tree is perfect, i.e. each non-leaf node has exactly $2$ children.