Serialize And Deserialize Binary Tree

Serialize: walk the tree in preorder (node, then left, then right), appending each value to a list, and appending a sentinel ('#') wherever a child is None. Join with commas into one string.

Deserialize: split the string back into tokens and consume them with an iterator, in the same preorder order they were written: read one token as the current node’s value (or None if it is the sentinel), then recursively build its left subtree, then its right — the iterator’s position naturally stays in sync because both sides visit nodes in the same order.

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Codec:
    def serialize(self, root: TreeNode | None) -> str:
        values = []

        def dfs(node: TreeNode | None) -> None:
            if node is None:
                values.append("#")
                return
            values.append(str(node.val))
            dfs(node.left)
            dfs(node.right)

        dfs(root)
        return ",".join(values)

    def deserialize(self, data: str) -> TreeNode | None:
        tokens = iter(data.split(","))

        def build() -> TreeNode | None:
            token = next(tokens)
            if token == "#":
                return None
            node = TreeNode(int(token))
            node.left = build()
            node.right = build()
            return node

        return build()

Serialization turns that tree into the string 1,2,#,#,3,4,#,#,5,#,#. The harder half is decoding that string back into an identical tree — trace it below. Watch the single moving pointer eat one token at a time: each number spawns a node, and each # closes a subtree so the pointer falls back to the sibling or parent. That one pass over the string, in the same preorder order the serializer wrote, is enough to rebuild the exact shape.

Deserializing reads that same string left to right: 1 becomes the root, then the next token (2) becomes its left child; since 2’s own next two tokens are both #, 2 is a leaf, and the reader falls back to 1’s right child, reading 3, and so on — the comma-separated order alone is enough to rebuild the exact shape.

Complexity: both serialize and deserialize visit every node (and every None child slot) exactly once, doing O(1) work each → O(n) time for each operation. The output string and the recursion stack both hold O(n) elements → O(n) space.

An alternative that mirrors LeetCode’s own display format: serialize with a queue, level by level, emitting '#' for None children (but not recursing into them). Deserialize the same way, pulling two tokens per queue entry to attach as left/right children.

from collections import deque

class Codec:
    def serialize(self, root: TreeNode | None) -> str:
        if root is None:
            return ""
        values = []
        queue = deque([root])
        while queue:
            node = queue.popleft()
            if node is None:
                values.append("#")
                continue
            values.append(str(node.val))
            queue.append(node.left)
            queue.append(node.right)
        return ",".join(values)

    def deserialize(self, data: str) -> TreeNode | None:
        if not data:
            return None
        tokens = data.split(",")
        root = TreeNode(int(tokens[0]))
        queue = deque([root])
        i = 1
        while queue:
            node = queue.popleft()
            if tokens[i] != "#":
                node.left = TreeNode(int(tokens[i]))
                queue.append(node.left)
            i += 1
            if tokens[i] != "#":
                node.right = TreeNode(int(tokens[i]))
                queue.append(node.right)
            i += 1
        return root

Why consider this: same O(n) time / O(n) space bounds as the DFS version, but the resulting string reads level by level, which is easier for a human to eyeball and matches the array format LeetCode itself uses to describe trees. The DFS version is generally preferred in practice for its shorter, purely recursive implementation.