Lesson 34 — Trees VII: Trees as Strings

~20 minutes · Day 40 · preorder + null markers · Python

Tonight's tree problem is Serialize and Deserialize Binary Tree. Interviewers like it because it tests whether you understand tree shape, not just tree values. A tree stored as memory pointers cannot be sent through a file, API, or database directly, so the interview version asks you to turn the tree into a string — and then rebuild the exact same tree from that string.

The invariant

Preorder with explicit null markers is unambiguous — the string rebuilds exactly one tree.

That's the whole idea. If you write only the real node values, the shape can disappear. The values 1,2 could mean a root with a left child, or a root with a right child. The missing children matter. So the string must record them.

The # token records which child pointer was empty, so the decoder does not guess the shape.

The slow way first

A tempting brute force is: write a preorder list of only real node values, then make the decoder guess where the missing children were. That is slow and still not a real decoder. It may build a tree, but not necessarily the original tree, because several shapes can share the same value order.

1
 \
  2

1
/
2

Both trees above have the same values in preorder: 1,2. The fix is not a cleverer guess. The fix is to store the missing children as tokens too. Python's str.split can turn a comma-separated string back into tokens; after that, one shared iterator lets the recursive rebuild consume those tokens from left to right.

The null-marker way

Walk the tree in preorder: node, left, right. When you hit an empty child, write #. During rebuild, read one token. A # means “this child is empty.” A number means “create this node, then rebuild its left child, then rebuild its right child.”

The token stream is a to-do list for recursion: read one token, then immediately finish that token's left and right subtrees.

class Codec:
    def serialize(self, root):
        out = []
        def dfs(node):
            if not node: out.append("#"); return        # record empty child
            out.append(str(node.val)); dfs(node.left); dfs(node.right)
        dfs(root); return ",".join(out)                 # one preorder string
    def deserialize(self, data):
        vals = iter(data.split(","))                    # consume left to right
        def build():
            v = next(vals)
            if v == "#": return None                    # rebuild empty child
            node = TreeNode(int(v)); node.left, node.right = build(), build(); return node
        return build()

The trust move is pure tree recursion: let recursion handle each subtree. At one node, you only decide whether the next token means “empty child” or “real node.”

Transfer: same idea, reverse direction

Predict first: what tree does this string rebuild?

1,2,#,#,3,#,#

  1
 / \
2   3

What the markers buy you

The marker version visits each token once. The string stores every real node and every empty child marker, so the cost grows linearly with the tree.

Practice — answer before you scroll past

def dfs(node):
    if not node:
        return
    out.append(str(node.val))
    dfs(node.left)
    dfs(node.right)

Your move (tonight)

Solve this on LeetCode, logging it in your Notion tracker with the cycle — predict → attempt → compare → encode:

1. Serialize and Deserialize Binary Tree — before coding, say the invariant out loud and hand-run the string for a three-node tree. Then implement preorder with # null markers.

For the encode step, write the invariant from this page in your own words. Revision day should test whether you can rebuild the serializer and deserializer from that one sentence.