Let $T$ be a maximal heap tree. Let $T$ hold the integers $1$ to $n$ as its nodes without duplicates. Let $x$ be a child of the root. What are the possible values that $n$ could take, in terms of $x$?
Clearly $x$ is not the maximum, so $n$ is greater than $x$. But I'm struggling with a more concrete description of all the possible values $n$ could be in terms of $x$.
The biggest possible number is clearly $n-1$.
Let $t = 2^{\lfloor \log_2(n)+1 \rfloor}$.
The size of the tree without the last layer is $t-1$.
We have $\min(\frac{t}{2}, n-t)$ nodes on the additional layer of the left subtree and $\max(0, n-t-\frac{t}{2})$ on the additional layer of the right subtree.
So the size of the left subtree is $\frac{t}{2} -1+ \min(\frac{t}{2}, n-t)$, and the size of the right tree is $\frac{t}{2} -1+ \max(0, n-t-\frac{t}{2})$
Each child of the root must be bigger than all the number in the corresponding subtree, so at least $\frac{t}{2}-1 + \max(0, n-t-\frac{t}{2})$ (the right subtree is the smallest one).
This can be easily achieved by filling the tree from the maximal value to the minimal one with a DFS.
