Serialize and Deserialize Binary Tree — The Bonsai Courier

Boss 15: The Bonsai Courier

The final boss, and fittingly, it isn't a puzzle, it's an engineering rite. Serialization is how trees escape RAM: how they cross networks, land on disks, survive restarts. Every JSON payload, every protobuf, every database page is a cousin of what you build here. LeetCode calls it Hard; you'll call it Boss 13's loophole plus writing discipline.

The story

The champion bonsai "Winter Cloud" must move from a greenhouse in the east to a museum in the west. Live transport is out: too fragile, too slow. The courier's exotic alternative: transmit the tree as text, regrow it on arrival. Identical. Not similar, identical, judges will compare it branch for branch against photographs. Empty spots included: a bonsai's art is as much where branches aren't.

Boss 13 taught the obstacle: one traversal, values only, can't pin down a shape. [3, 9, ...] couldn't say whether 9 hung left or right. That's why the journals came in pairs.

And Boss 13's callout planted the loophole: pairs are needed only because plain traversals skip the empty spots. Record the Nones, and the flattening loses nothing. One journal, with gaps marked, determines the tree completely.

The tree:

        1
       / \
      2   3
         / \
        4   5

Write it down pre-order (self, left, right), marking every empty spot with #:

1,2,#,#,3,4,#,#,5,#,#

Read it aloud like the botanist regrowing it: "1. Its left: 2. 2's left: nothing. 2's right: nothing. So back to 1's right: 3. 3's left: 4..." Every question the regrower could ask, the line answers at the exact moment it's asked. No searching, no directory, no second journal. That's what recording the gaps buys.

The problem, dressed up properly

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.

LeetCode 297. The freedom ("no restriction") is real, and so is the responsibility: you are designing a format, and formats have failure modes.

The naive attempt

Two journals! Serialize pre-order and in-order, ship both, rebuild with Boss 13's machinery.

It genuinely works... on that problem's guarantee: unique values. This problem makes no such promise, and Boss 13's directory (value → position) collapses when two branches share a value. A bonsai with two identical "5" branches ships east and regrows west as something else. The two-journal scheme isn't wrong, it's fragile, resting on a guarantee this contract doesn't give. The gap-marking scheme needs no such crutch: it never looks anything up by value.

(The other naive road: level-order with gaps, LeetCode's own bracket format. Perfectly valid, queue-based, slightly bulkier. The DFS version below is less code and pairs with everything this dungeon taught.)

The weapon: pre-order with the gaps written down

Serialize is Boss 1's skeleton with a notebook: visit self (write the value), recurse left, recurse right, and when there's no node, write the mark.

Deserialize is where the design earns its keep: read tokens one at a time through a single shared cursor, exactly Boss 13's cursor discipline:

• Read a token. If it's #: this spot is empty, return None, done.
• Otherwise: it's a node. Build it, then, because the format is self-left-right, everything next on the line is its left subtree; recurse, then recurse right.

The deep symmetry, and the reason this boss closes the dungeon: serialization and deserialization are the same traversal, one writing the line, one reading it. The writer's recursion and the regrower's recursion visit spots in the identical order, so the line's tokens arrive precisely when the regrower needs them. The format is the traversal. Once you see that, every serializer you meet, JSON's nested braces included, reads as a traversal wearing punctuation.

Watching it work

Regrowing 1,2,#,#,3,4,#,#,5,#,#:

read 1  → node(1); regrow its left
  read 2  → node(2); regrow its left
    read # → None (2's left is a gap)
    read # → None (2's right)
  ← 2 complete
  back at 1: regrow its right
  read 3  → node(3); regrow left
    read 4  → node(4)
      read #, read # → both gaps
    read 5  → node(5)
      read #, read # → both gaps
  ← 3 complete
← 1 complete. Winter Cloud stands.

Eleven tokens, eleven questions, zero ambiguity. Count them: 6 values + 5 marks... a tree with n nodes has exactly n + 1 gaps (each node offers 2 spots, each non-root node fills 1: 2n - (n-1) = n+1). Your serialized line should always have that shape; it's a free sanity check on any implementation.

The code

class Codec:
    def serialize(self, root: TreeNode | None) -> str:
        out = []
        def write(node):
            if not node:
                out.append("#")
                return
            out.append(str(node.val))
            write(node.left)
            write(node.right)
        write(root)
        return ",".join(out)
 
    def deserialize(self, data: str) -> TreeNode | None:
        tokens = iter(data.split(","))
        def read():
            tok = next(tokens)
            if tok == "#":
                return None
            node = TreeNode(int(tok))
            node.left = read()
            node.right = read()
            return node
        return read()

iter() + next() is the shared cursor, Python's iterator protocol handing out tokens in order. In other languages: an index passed by reference, or a queue you pop from the front.

Gotchas

1. Skipping the gaps. The entire boss. Values-only pre-order is Boss 13's ambiguity, reborn. If your deserializer needs to guess or search, your format lost information.

2. Separator-free concatenation. The 1,12 vs 11,2 collision. Join with a delimiter, split on it, never substring-parse by position.

3. Two cursors, or a reset cursor. The left-subtree recursion and right-subtree recursion must consume from the same advancing cursor. A fresh iterator per call, or an index passed by value, regrows the same branch everywhere.

4. The empty bonsai. root = None serializes to "#" and must regrow as None. Formats that special-case emptiness with empty strings then crash splitting them. One mark, no special case, test it.

5. Deserializing untrusted lines. Interview scope ends at "round-trips correctly". Production scope doesn't: a malformed line ("1,2", truncated) makes next(tokens) raise, and real formats carry length checks and version tags. Saying this sentence out loud in an interview is worth more than it costs.

Complexity

Each spot, node or gap, written once and read once.

Time: O(n) both directions. Space: O(n) for the line, O(h) for the recursion.

Boss down. DUNGEON DOWN. XP gained. Level up.

Winter Cloud regrows in the museum, and the judges' loupes find nothing to object to: every branch, every deliberate emptiness, exactly as photographed. The line of text is framed beside it.

Fifteen bosses. What you're carrying out of Dungeon 7, the biggest haul of the quest:

• The incantation: base case, one node's work, trust the recursion, and its four traversal orders, all with faces now
• Answers up through returns (depth, counts, arms), context down through arguments (maxes, ranges), and side channels for prizes that live anywhere (diameter, gold)
• The clamp, the sentinel, and the two zeros, small tools that decide Hard problems
• BST ordering: navigation instead of search, in-order as sorted order, territories not children
• BFS: the queue, the snapshot, and the per-level family
• Construction: recursion that returns nodes, cursors that consume traversals, and formats that record their gaps
• The meta-lesson, twice proven: Hards are compositions, Boss 14 was 3+10, Boss 15 was 1+13

Next dungeon: Tries. The tree grows letters. Twenty-six children per node instead of two, words stored as paths from the root, and shared prefixes shared exactly once. Autocomplete, spell-check, and prefix search in O(word length), plus a wildcard boss that brings recursion right back. The trees keep branching.

See you in Dungeon 8.