Introduction to Serialize and Deserialize Pattern

You need to send a binary tree to another machine. A network carries bytes, not objects, so the tree must become a string and then be rebuilt exactly.

The first idea is to write the values in preorder: root, then left, then right.

    1              preorder:  1, 2, 3, 4, 5
   / \
  2   3
     / \
    4   5

That string cannot be rebuilt. Several different trees produce 1, 2, 3, 4, 5 in preorder, and nothing in it says where each subtree ended.

The missing information is the shape, and the shape lives in the empty places. Write those down too, using a marker for a missing child