Design two functions. One turns a binary tree into a string, and the other turns that string back into the same tree.
DSA Animator › DSA Revision › Tree › Serialize and Deserialize Binary Tree
Remember: preorder plus null markers describes a tree completely. Read the tokens back in exactly the order you wrote them. The video solves Serialize and Deserialize Binary Tree (LeetCode 297, Hard) with the Preorder with Null Markers pattern from the Tree topic, and you can replay every step in the interactive Serialize and Deserialize Binary Tree animation.
Design two functions. One turns a binary tree into a string, and the other turns that string back into the same tree.
For the tree 1, with children 2 and 3, where 3 has children 4 and 5, one valid string is 1, 2, hash, hash, 3, 4, hash, hash, 5, hash, hash. Each hash marks an empty child.
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.
Serialize: write 1, then go left and write 2. Both children of 2 are empty, so write two hashes. Back at 1, go right and write 3, then 4 with two hashes, then 5 with two hashes. Deserialize: read 1 and create the root, then read 2 for its left child. Two hashes end the subtree of 2, so the next token, 3, becomes the right child of 1. 3 reads 4 and its two hashes as its left side, then 5 and its two hashes as its right side. The tree is exactly the original.
In code, serialize appends the value and a comma, or a hash and a comma, in preorder. Deserialize splits the string into a queue of tokens. A recursive build polls one token, returns null for a hash, otherwise creates a node and builds its left and then its right. Both directions are O of n time and space.
Remember: preorder plus null markers describes a tree completely. Read the tokens back in exactly the order you wrote them.