Daily bit(e) of C++ | Serialize and de-serialize n-ary tree
Daily bit(e) of C++ #51, Common C++ interview problem: serialize and de-serialize an n-ary tree.
Today we will look at a common C++ interview problem: serializing and de-serializing an n-ary tree.
Given a tree data structure, we must implement stream extraction and insertion operations to serialize and deserialize the tree.
The choice of format is part of the problem. Each node stores a uint32_t value and a vector of weak pointers to children. To add a node to the tree, use the add_node method (the method will set the tree root when the parent is nullptr).
Before you continue reading the solution, I recommend you solve it yourself. Here is a link to Compiler Explorer with a couple of test cases: https://compiler-explorer.com/z/M6Mx9qxfn.
Solution
There are many possible approaches, as we can choose any format for serialization.
I have chosen a straightforward recursive pre-order traversal combined with a “terminal value” format.
Each list of children terminates with a “-1” value (outside the domain of uint32_t). For example, a single node tree with a root value of 0 serializes into "0 -1".
For an empty tree, we can either serialize as "-1" or leave the output unchanged.
The former has the benefit of explicitly denoting an empty tree, allowing us to store a specific number of empty trees in serialized form (where an empty output is simply empty).
Deserializing is then a matter of reading input until we read a negative value (again, using a recursive pre-order traversal).