Serialize And Deserialize A Given N-Ary Tree

So for the tree depicted above, the serialized representation is: For my Python code, the serialized representation is going to be a list of 'entries', each entry being either None (to specify the 'null node' from the description above), or a pair of (data, has_children_flag), with data being the tree node data, and has_children_flag a boolean specifying whether this node has children. A chain of sibling entries is terminated by a null node.Īfter a couple of minutes of thought it should become obvious that this indeed creates a serialized representation that is reversible.

Additional children are represented as siblings of the first child. If a node is defined to have children, the next physically succeeding node is its first child. If a node is defined not to have children, the next physically succeeding node is a sibling. Each node is defined either to have children or not to have children. The tree itself is represented by flattening it in prefix order.

Here's a quote from the DWARF v3 standard section 2.3 explaining it, slightly rephrased:

Serialize And Deserialize A Given N-Ary Tree