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.

enter image description here


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.