DSAPrep
HardTrees

Serialize And Deserialize Binary Tree

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.

Clarification: The input/output format used here is just for illustration purposes, you do not necessarily need to follow this format, so feel free to come up with a different approach.

Example 1

Input: root = [1,2,3,null,null,4,5]
Output: [1,2,3,null,null,4,5]

Example 2

Input: root = []
Output: []

Constraints

  • The number of nodes in the tree is in the range [0, 10^4].
  • -1000 <= Node.val <= 1000
View original on LeetCode ↗

Serializing a tree needs to preserve shape, not just values — so None children must be encoded explicitly, not just dropped, or the deserializer would not know where each subtree ends. Any traversal order works as long as encode and decode agree on it; a pre-order DFS makes decoding especially clean because each value is immediately followed by everything needed to rebuild its own subtree.

Preorder DFS with Null Markers

OptimalTime O(n)Space O(n)

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()

Tracing serialization of root = [1,2,3,null,null,4,5] (tree: 1 has children 2 and 3; 2 is a leaf; 3 has children 4 and 5):

1
2
3
4
5
1 / 4
seenresultcurrent

Visit 1 (preorder: node first). Append "1". Recurse left.

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.

BFS Level-Order with Null Markers

Time O(n)Space O(n)

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.