Serialization of binary tree - PrismoSkills
Solution 2: An approach specific to trees is that you write out both the pre-order and in-order traversal of the tree and then reconstruct the tree by reading both these orders.
Solution 3: If we have a special marker for null child, then pre-order or level-order traversal can be used to serialize a tree and it can be easily deserialized in O(n). The special null markers help to terminate the branches and leave no room for ambihuity when constructing the tree. The same is not possible in post-order or level-order traversals because there children are printed first.
Solution 4: Can you restore the tree by storing level of each node along with in-order traversal of the tree? Just in-order traversal is not sufficient because given an incomplete tree, next node can be added anywhere (even if we have to add it in in-order fashion). So if level is fixed, then can we restore the tree completely?
Read full article from Serialization of binary tree - PrismoSkills
