Uniform Subtrees

the input is a tree, and the output graph is also a tree (with the longest chain and most nodes on the left hand children).

Consider this input: (((()()))(()()())) (encourage drawing it out)

The "output" Is 0 10 110 1110 1120 120 130 20 210

This maps to a tree of the following form: (((()())()())(())) (again encourage drawing it out)

whose preorder traversal defines the output. (number each edge from each node from left to right to see this)

If we have two subtrees in this form, we can "merge" them by walking them. Any time tthere is an edge which exists in the right subtree, but not the left, we "move" that edge to the left subtree. In this case, note how two of the "three" edges from the right subtree moved to the left. This merge process leaves the combined tree in the correct form, enabling us to further merge in more subtrees, so we do this process recursively.