LeetCode #297 Hard

Serialize and Deserialize Binary Tree

Encode a binary tree to a string and decode it back exactly.

treedfsdesign

02

Intuition

💡

Preorder with explicit null markers is unambiguous: the nulls pin down where subtrees end, so the same recursion that wrote the string can replay it. Serialization is a preorder dump; deserialization is the mirror-image recursive read.

03

Approach

1

Serialize: preorder + '#' for null

dfs(node): emit val, recurse left, recurse right; emit # at nulls. Join with commas (handles multi-digit and negatives).

2

Deserialize: consume in the same order

Read the next token: '#' → None; else make the node and build left then right. An iterator carries the position implicitly.

3

Why it round-trips

Preorder with nulls encodes the exact shape — no inorder needed, unlike the classic two-traversal reconstruction.

04

Solution & live demo

python

▶1class Codec:
▶2    def serialize(self, root):
▶3        out = []
▶4        def dfs(node):
▶5            if not node:
▶6                out.append("#"); return
▶7            out.append(str(node.val))
▶8            dfs(node.left); dfs(node.right)
▶9        dfs(root)
▶10        return ",".join(out)
▶11 
▶12    def deserialize(self, data):
▶13        tokens = iter(data.split(","))
▶14        def build():
▶15            t = next(tokens)
▶16            if t == "#": return None
▶17            node = TreeNode(int(t))
▶18            node.left = build()
▶19            node.right = build()
▶20            return node
▶21        return build()

05

Edge cases

Empty tree

Serializes to "#" and decodes to None.

Negative / multi-digit values

Comma delimiting keeps tokens intact — never parse per character.

06

Complexity

Time

O(n)

Space

O(n)

One pass each way; string size O(n).