Simple and succinct flattened trees

A tree is a node with a list of zero or more trees as children. This is a more complex and flexible structure than a list, but a list has just as many edges between items as a tree, so you can convert between them.

You could show each node followed by a pair of parentheses, with its children between those.

Then that tree would be shown as 2(7(2()10()6(5()11()))5(9(4()))). This method is obvious but ugly: for each node, we must use two separate symbols, which may end up far apart in the string. We can do better.

The preorder traversal of a tree lists a node followed by the preorder traversal of its children. To rebuild the tree from that list, you must know where each child-list starts and ends. Each node can start its list of siblings, or end it, or both (if it's in the middle), or neither (if it's the only child).

Thus each node must be marked with one of four symbols. Let's call them "drop", "top", "hop", and — to complete the rhyme — "bop". The names come from what you must do to the node so marked, as you step thru the list:

• if "drop", add the node as the first child of the last one
• if "top", add the node as a sibling to the last one, and plan to retreat to its parent when you return to this node
• if "hop", add the node as the first and only child of the last one, retreating at next visit like "top"
• if "bop", add the node as a sibling of the last one

E.g. the tree shown above flattens this way as 2H 7D 2D 10B 6T 5D 11T 5T 9H 4H.

This method uses just one symbol per node.

A D/T/H/B string validly represents a tree iff each D is matched by a later T (and vice versa), and any Bs are between at least one D-T pair. Aliter: treat D as up-up, T as down-down, H as up-down, and B as down-up.

Then a string is valid iff that path ends at the same height as it starts, and always stays above its starting height. These are Dyck paths are counted by Catalan numbers also count trees, strongly suggesting that this D/T/H/B form suffices for all trees.