Watrophy: code challenges by Robert Smith

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.

#36: Falling Leaves