Serialize and Deserialize Binary Tree

Problem

Design an algorithm to serialize a binary tree to a single string, and deserialize that string back to the exact original tree structure (values, and where every null child is). No assumption may be made about the tree's shape or values — the design must work for any binary tree. (LeetCode 297.)

Examples

      1
     / \
    2   3
       / \
      4   5

The string encoding is yours to choose — only the round-trip must hold.

Constraints

up to 10⁴ nodes · values may be any 32-bit integer · encoding must not conflate real values with a null sentinel

Attempt it first

The previous lesson (Construct from Preorder and Inorder) needed two traversals to reconstruct a tree, precisely because a single traversal without extra information can't reveal where nulls are — many different tree shapes can share the same plain preorder sequence. This problem's whole trick is: what if the traversal explicitly records nulls too? Before opening anything, work out why recording explicit null markers during a SINGLE preorder pass makes that pass, on its own, sufficient to reconstruct the exact tree — no second traversal required.