Serialize and Deserialize Binary Tree

Convert a tree to text and rebuild the same tree from that text.

Start with the concrete trace below. It shows the state the algorithm must carry as it runs.

Problem trace

Serialize and Deserialize Binary Tree: Preorder records each node and each missing child, so the decoder can consume one token per recursive slot and recover the exact topology.

Input and goalConvert a tree to text and rebuild the same tree from that text.

Initialize preorder at the rootFor root 1 with left leaf 2 and right child 3 whose left child is 4, visit(1) appends 1.

visit 110213243

stream[1]callStackvisit(1)activeStatevisit 1topology1 -> 2, 1 -> 3, 3 -> 4

Recognize it

Use structural sentinels when a tree must round-trip through a linear stream and node values alone do not uniquely identify its shape.

Keep true

Each recursive serialize call emits exactly one leading token for its slot, and each deserialize call consumes exactly one leading token before recursively rebuilding the same left and right slots.

Reuse it

To encode recursive structure linearly, emit a token for every recursive slot, including empty ones, and make the decoder consume tokens in the identical traversal order.

Pattern: Preorder DFS with markers for missing children.

Simple idea: Preorder alone is not enough because shapes can differ. Save # for every missing child. The decoder follows the same order.

class TreeCodec:
   def serialize(self, root: TreeNode | None) -> str:
      values: list[str] = []

      def visit(node: TreeNode | None) -> None:
         if node is None:
            values.append("#")
            return
         values.append(str(node.val))
         visit(node.left)
         visit(node.right)

      visit(root)
      return ",".join(values)

   def deserialize(self, data: str) -> TreeNode | None:
      values = iter(data.split(","))

      def build() -> TreeNode | None:
         value = next(values)
         if value == "#":
            return None
         node = TreeNode(int(value))
         node.left = build()
         node.right = build()
         return node

      return build()

Cost: $O(n)$ time and $O(n)$ space.

The platform supplies TreeNode with val, left, and right; this snippet assumes that definition.