What are these tree transformations called?

Question

I want to transform a general rooted, node-labeled tree into a related binary tree. I came up with four different schemes ("left shallow", "right shallow", "left deep" and "right deep" binarization) that are illustrated by an example in the diagram below. They all preserve certain aspects of the original structure. Children stay children or become grand- (or grand-grand or grand*-)children. Also, new nodes are introduced (depicted in blue), which is fine for my application.

Does any of these four schemes have a name? Or is it documented or studied somewhere?

I am aware of one documented "binarization" scheme, which is called Knuth transform (also in the diagram). It is also possible to recover the original tree from this and you don't even have to introduce new nodes while building the binary tree. However, I am not interested in this, since it brings former siblings into parent-child-relation, which I can't have in my application.

Answer 1

The Natural Language Toolkit (NLTK) offers binarization: nltk.treetransforms.chomsky_normal_form(). The algorithm in NLTK implements the standard, straight-forward transformation into Chomsky normal form. It assumes the tree was generated via an underlying (context-free) grammar. This results in the deep trees in the bottom row (diagram in the question post). By default, you will get the "right deep" variant, as a consequence of putting the artificial non-terminals on the right of the existing non-terminals ("right factorization") when transforming the production rules. You can change the default parameter factor="right" to factor="left", if you prefer the "left deep" variant.

However, this is not the only way to construct a grammar in Chomsky normal form, since it only requires to have production rules of the form $A\to BC$ (or $A\to a$). You could just as well decide to balance the two sets of children as well as possible and assign them to the artificial nodes on the left and right. Since children can come in odd numbers, you will have to decide to add one more to either side. If you put it on the left, you will get the "left shallow" variant, and the "right shallow" variant otherwise.

For this other algorithm to arrive at a Chomsky normal form (that produces the "shallow" variants) I could not find a term. This is likely because Chomsky normal form comes from the world of theoretical computer science and it is most useful as an existential fact ("there exists a certain normal form, s.t. ...") where the details matter little. I think "balanced factorization" would be an appropriate term for this transformation.

The library Discontinuous Data-Oriented Parsing offers more binarization schemes with a confusing set of options. This includes the algorithm from NLTK and approaches described in two papers. The library deals with natural language parsing via Linear Context-Free Rewriting Systems (LCFRS) (a generalization of Probabilistic Context-Free Grammars (PCFG)), and a lot of options might related to this specific application. I was not able to get a "shallow"/"balanced" binarization from this library, but it might be possible.