Serialize / deserialize by BFS

57 s · title card, the worked example step by step, then a recap. The captions carry the explanation; there is no narration. Download the MP4.

01The intuition

Start with what you would do by hand

You have a binary tree and need to send it to a friend as text, so that the friend can rebuild exactly the same tree. The tree has 1 at the root, children 2 and 3, and 3 has children 4 and 5. Writing the values in order, 1 2 3 4 5, is not enough: the friend cannot tell whether 4 hangs under 2 or under 3. The shape is missing. By hand you might draw it, but text has no drawing, so the shape must be encoded in the sequence itself.

The missing information is where the gaps are. Node 2 has no children; if we write that down, the friend will know that 4 and 5 cannot belong to 2.

Build the structure, one piece at a time

Piece one: level order with a queue. Start with the root in a queue; repeatedly take the front node, write its value, and push its left child then its right child. This visits the tree one level at a time: 1, then 2 and 3, then 4 and 5.

Piece two: a marker for a missing child. When a child is missing, push a placeholder anyway, and when the placeholder reaches the front write # and push nothing. Now the sequence records every gap:

The remaining four markers are trailing and can be dropped. The text is "1 2 3 # # 4 5".

Piece three: rebuilding. Read the first token as the root and put it in a queue. Then repeatedly take the front node and give it the next two tokens as its left and right children, creating a node for a value and nothing for #, and pushing each created node onto the queue. Node 1 takes tokens 2 and 3; node 2 takes # and #; node 3 takes 4 and 5; nodes 4 and 5 find no more tokens, so they are leaves. The tree is back, shape and all.

Why it is correct

The invariant during serialisation is that the queue holds, in order, the nodes and gaps of the current level not yet written, and every written node has had its two child slots pushed. So the output lists, level by level, every slot of the tree, with # standing for empty slots. During rebuilding, the invariant is that the i-th non-marker token written was pushed to the queue as the i-th real node, and its two child slots are the tokens that were written when it was popped. Because the serialiser pushes exactly two slots per real node and the rebuilder consumes exactly two tokens per real node in the same order, each node receives exactly the children it had. Dropping trailing markers is safe because a missing token at the end means an empty slot.

Why it is fast

Serialising pops each node once and each empty slot once. A binary tree with n nodes has n + 1 empty child slots, so the queue handles 2n + 1 entries and the text has at most 2n + 1 tokens:

tokens = n nodes + (n + 1) markers = 2n + 1

Rebuilding reads each token once and creates each node once. Both directions are O(n) time and O(w) extra memory for the widest level w, beyond the output itself. A preorder encoding with the same # markers works equally well with a recursive reader; level order is chosen when the input format is level order already, as it is on LeetCode.

How to recognise it in an interview

Cues: "serialize", "deserialize", "encode the tree as a string", "send over the network", "N-ary tree to binary tree". Say: "I will write a level-order traversal with an explicit marker for every missing child, so the shape survives, and rebuild with a queue of parents consuming two tokens each".

Serialize and Deserialize Binary Tree is the walk-through above. Serialize and Deserialize N-ary Tree writes each node followed by its number of children, so the reader knows how many tokens to consume instead of always two. Serialize and Deserialize BST can omit the markers entirely, because a preorder of a BST is enough to rebuild it using value bounds.

02The idea in one line

Write nodes level by level with null markers; rebuild with a queue of parents.

Reach for it when: Serialize and deserialize binary tree, N-ary tree, tree codec with nulls.

Cost: O(n) time.

03The walk-through, step by step

The video works one example: Serialize [1,2,3,null,null,4,5] by level. These are its captions in order, so you can follow without the video or check a step you missed.

1. Serialize: BFS, writing # for a missing child so the shape survives
2. pop 1: write 1, enqueue both children (2, 3)
3. pop 2: write 2, enqueue both children (#, #)
4. pop 3: write 3, enqueue both children (4, 5)
5. pop a null: write # (it has no children to enqueue)
6. pop a null: write # (it has no children to enqueue)
7. pop 4: write 4, enqueue both children (#, #)
8. pop 5: write 5, enqueue both children (#, #)
9. Serialized: 1 2 3 # # 4 5 (trailing nulls can be dropped)
10. Deserialize: each parent takes the next two tokens as children
11. Token 0 is the root; put it in the queue
12. parent 1 takes tokens 1 and 2: 2 and 3
13. parent 2 takes tokens 3 and 4: # and #
14. parent 3 takes tokens 5 and 6: 4 and 5
15. The tree is rebuilt exactly, nulls and all
16. Both directions visit each node once: O(n)

04Asked at Google

3 Google-tagged LeetCode problems use this pattern. Frequency is LeetCode's Google-tag score (higher means reported more often); "last 6 months" marks problems reported in the most recent window of the export.

05Related patterns

Other patterns in Trees: Recursive DFS (post-order fold), Best path through each node, Level-order BFS, Root-to-leaf path carry, Lowest common ancestor, Build from traversals, Iterative traversal with a stack, Column / coordinate traversal, Rerooting DP (sum over all roots), Post-order deletion / pruning, Tree as a graph (parent pointers), Tree DP: take or skip this node.