#297HardTrees & BST

Serialize and Deserialize Binary Tree

The tell: Round-trip a tree through a string, so the encoding must be unambiguous.

How you get there

1A single traversal without null markers does not determine the shape.
2Pre-order with explicit nulls does, because each position is accounted for.
3Deserialisation consumes the same sequence in the same order.

Solution

Python

def serialize(root) -> str:
    parts: list[str] = []

    def walk(node) -> None:
        if not node:
            parts.append("#")
            return
        parts.append(str(node.val))
        walk(node.left)
        walk(node.right)

    walk(root)
    return ",".join(parts)

def deserialize(data: str):
    values = iter(data.split(","))

    def build():
        token = next(values)
        if token == "#":
            return None
        node = TreeNode(int(token))
        node.left = build()
        node.right = build()
        return node

    return build()

Time: O(n)
Space: O(n)

What goes wrong

Omitting null markers makes many different trees encode identically, so the round trip is lossy.

Test yourself on DSA Next: Diameter of Binary Tree →