Remove the root from a binomial tree

Question

I have a binomial tree with height k.

How do I proof that when I remove the root, the result will be k new binomial trees, each with with a height from 0 to k-1.

Thanks in advance.

Answer 1

If your definition of "binomial tree is that geiven in Wikipedia (see Binomial Heap) it is defined recursiveley:

• A binomial tree of order 0 is a single node
• A binomial tree of order k has a root node whose children are roots of binomial trees of orders k−1, k−2, ..., 2, 1, 0 (in this order).

And a binomial tree of order $k$ has height $k$.

Thus what you need to prove follows trivially if the original tree has height 0; when you remove the (only) node, you are left with 0 trees.

And the second point of the definitions tells you what happens when you remove he root (leaving all the children as disjoint trees) of a tree of order $k > 0$. That exactly matches the statement you need to prove.