Design an algorithm to serialize a binary tree to a string and deserialize that string back to the original tree. Use BFS (level-order) with "null" tokens for missing nodes.
root = [1,2,3,4,5]"1,2,3,4,5,null,null,null,null,null,null,"rebuilds original tree exactlyroot = [1,null,2,null,null,null,3]"1,null,2,null,null,null,3,...""null" for missing nodesBFS serialization produces level-order output including nulls. Deserializing BFS output works because we know each parent's children occupy exactly the next two positions in the token stream — null tokens mark absent children. The BFS queue keeps parents and children in perfect sync: each dequeued parent consumes exactly two tokens, and each non-null token produces exactly one new child to enqueue.
Storing only the preorder values is not enough, because different shapes can share the same preorder. Recording the empty children as well makes the shape unique.
To serialize, do a preorder traversal. Write each value, and write a hash for every null child. To deserialize, read the tokens in the same preorder. A hash means null, and any number creates a node whose left and right children are read next, in that order.
Preorder plus null markers describes a tree completely. Read the tokens back in exactly the order you wrote them.
Run the animation above on your own input, or watch the 2:09 video explanation of Serialize and Deserialize Binary Tree with a dry run and Java code.