Tagged as challenge

Written on 2018-02-08

Imagine you have a $k$-ary rooted tree $T$ defined by the following diagram:

```
[ A ]
[ / \ ]
[ B C ]
T := [ / \ / \ ].
[ D E F G ]
[ / \ \ ]
[ H I J ]
```

The leaves of $T$ are $$\operatorname{leaves}(T) := \{\mathtt{H}, \mathtt{I}, \mathtt{E}, \mathtt{J}, \mathtt{G}\}.$$ Imagine the leaves fall off though an operation called $\operatorname{fall}$ so that $\operatorname{fall}(T)$ is

```
[ A ]
[ / \ ]
fall(T) = [ B C ].
[ / / ]
[ D F ]
```

After another iteration, we get $\operatorname{fall}^2(T)$, which is

```
[ A ]
fall²(T) = [ / \ ].
[ B C ]
```

And $\operatorname{fall}^3(T) = \mathtt{A}$, the root.

Write a function which takes *any* $k$-ary rooted tree $T$ and prints
out the sequence
$$\ell_i(T) := \big(\operatorname{leaves}\circ\operatorname{fall}^i\big)(T)$$
for $0\leq i \leq n$ where $n$ is defined such that
$\operatorname{fall}^n(T)$ is the root of $T$. (Since it is a
sequence, it should be printed in order.)

For the example above, in somewhat abbreviated notation, we have $$\ell(T) := (\mathtt{HIEJG}, \mathtt{DF}, \mathtt{BC}, \mathtt{A}).$$

*Thanks to Steven Heidel for
telling me about this wonderful problem.*