Serialize and Deserialize Binary Tree (LeetCode 297)

The problem

Design a Codec with two methods:

• serialize(root) turns a binary tree into a string.
• deserialize(data) turns that string back into the exact same tree.

You choose the format. The only rule is that a round trip must give back an identical tree.

Input tree:     1
               / \
              2   3
                 / \
                4   5

serialize   -> "1,2,#,#,3,4,#,#,5,#,#"
deserialize -> the same tree, level order [[1], [2, 3], [4, 5]]

Each # marks a missing child. Node 2, for example, is followed by #,# because it has no children.

How to think about it

Why not just a traversal? A single preorder list like 1,2,3,4,5 doesn’t fix the shape: many trees share it. That’s why Construct from Preorder and Inorder needs two lists. Storing two traversals works, but it’s twice the data and needs unique values.

The key insight: write down the nulls too. If preorder also records every empty child as #, the shape is no longer ambiguous. When you read the stream back, each token tells you exactly what to do: a number means “make a node, then build its left subtree, then its right”; a # means “this subtree is empty, return”.

Deserialise in the same order you serialised. The writer did “node, left, right”. So the reader is the same recursion: read a token, and if it’s a value, recursively build left, then right. Consuming a shared iterator means each call takes exactly the tokens that belong to its subtree, so no index arithmetic is needed.

Which pattern is this? Tree DFS (preorder) used for encoding. The tell is “convert a tree to and from a string or list”. Level-order BFS with null markers (LeetCode’s own format) works too; preorder DFS is shorter to write.

Approach

Serialise:

1. Do a preorder DFS.
2. For an empty node, append "#". Otherwise append the value, then recurse left, then right.
3. Join the tokens with commas.

Deserialise:

1. Split on commas and wrap the tokens in an iterator.
2. dfs() reads one token. If it’s "#", return None.
3. Otherwise create the node, set left = dfs(), then right = dfs(), and return it.

Solution

class Codec:
    def serialize(self, root):
        out = []
        def dfs(node):
            if not node: out.append("#"); return              # record the null, so shape is kept
            out.append(str(node.val)); dfs(node.left); dfs(node.right)   # preorder: node, left, right
        dfs(root); return ",".join(out)
    def deserialize(self, data):
        vals = iter(data.split(","))
        def dfs():
            v = next(vals)
            if v == "#": return None
            node = TreeNode(int(v)); node.left = dfs(); node.right = dfs()   # same order as written
            return node
        return dfs()
# round-trip tree[1,2,3,null,null,4,5] -> same tree

Dry run

Deserialising "1,2,#,#,3,4,#,#,5,#,#". Each row is one token read:

All 11 tokens are used and the tree is [[1], [2, 3], [4, 5]] again.

Complexity

• Time: O(n) for both methods. Each node and each null marker is written or read once, and there are n + 1 null markers.
• Space: O(n). The string and the token list are O(n); the recursion stack adds O(h).

Edge cases and pitfalls

• Empty tree serialises to "#" and deserialises back to None.
• Negative and multi-digit values work because tokens are comma-separated and parsed with int. Without a delimiter, 12 and 1,2 would collide.
• Forgetting null markers is the classic bug: the round trip then silently builds the wrong shape.
• Very deep trees hit Python’s recursion limit. An iterative BFS codec avoids that.

Related problems

• Construct Binary Tree from Preorder and Inorder (LeetCode 105): rebuilding when you don’t have null markers.
• Encode and Decode Strings (LeetCode 271): the same “design a reversible format” thinking for a list of strings.
• Subtree of Another Tree (LeetCode 572): serialised trees turn subtree matching into substring matching.