Serialize and Deserialize Binary Tree

PracticeNeetCode ↗LeetCode ↗

Design an algorithm to serialize a binary tree into a string, and deserialize that string back into a tree with the exact same structure.

Example

Key Pointers

• A preorder traversal (root, then left, then right) is enough to reconstruct the tree exactly, as long as missing children are explicitly recorded — without those markers the structure is ambiguous.
• Serializing is a straightforward preorder DFS that writes a sentinel like "N" for a None child instead of skipping it.
• Deserializing rebuilds the tree by consuming tokens in the same left-then-right order they were written, using a shared iterator both recursive calls pull from.

Step-by-Step Analysis

1. Serialize: DFS the tree in preorder, appending str(node.val) for a real node or "N" for a None child, joined by commas.
2. Deserialize: split the string back into tokens and wrap them in an iterator.
3. Define a recursive build() that reads the next token; if it's "N", return None.
4. Otherwise create a TreeNode with that value, then recursively set node.left = build() and node.right = build().
5. Return the reconstructed root once the whole token stream has been consumed.

Complexity

Time: O(n) for both operations — Space: O(n)

Code

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

        def dfs(node: TreeNode | None) -> None:
            if not node:
                vals.append("N")
                return
            vals.append(str(node.val))
            dfs(node.left)
            dfs(node.right)

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

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

        def build() -> TreeNode | None:
            val = next(vals)
            if val == "N":
                return None
            node = TreeNode(int(val))
            node.left = build()
            node.right = build()
            return node

        return build()

Code Explanation

How the solution above works, piece by piece.

1. serialize does a preorder DFS: write the node's value, then serialize the left subtree, then the right.
2. Every missing child is written as "N". Without these markers, different shapes could produce the same list of values.
3. deserialize reads the values back in the same order with an iterator.
4. A value creates a node, then build() is called for its left and then its right child; "N" returns None, which tells the recursion where each branch ends.
5. Both directions are O(n) time and O(n) space.

Visual Walkthrough

Running it on root = [1, 2, 3, null, null, 4, 5]:

Video Explanation

NeetCode — Serialize and Deserialize Binary Tree, LeetCode 297