297. Serialize And Deserialize Binary Tree - Explanation

Description

Implement an algorithm to serialize and deserialize a binary tree.

Serialization is the process of converting an in-memory structure into a sequence of bits so that it can be stored or sent across a network to be reconstructed later in another computer environment.

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. There is no additional restriction on how your serialization/deserialization algorithm should work.

Note: The input/output format in the examples is the same as how NeetCode serializes a binary tree. You do not necessarily need to follow this format.

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:

0 <= The number of nodes in the tree <= 1000.
-1000 <= Node.val <= 1000

Recommended Time & Space Complexity

You should aim for a solution with O(n) time and O(n) space, where n is the number of nodes in the given tree.

Hint 1

A straightforward way to serialize a tree is by traversing it and adding nodes to a string separated by a delimiter (example: ","), but this does not handle null nodes effectively. During deserialization, it becomes unclear where to stop or how to handle missing children. Can you think of a way to indicate null nodes explicitly?

Hint 2

Including a placeholder for null nodes (example: "N") during serialization ensures that the exact structure of the tree is preserved. This placeholder allows us to identify missing children and reconstruct the tree accurately during deserialization.

Hint 3

We can use the Depth First Search (DFS) algorithm for both serialization and deserialization. During serialization, we traverse the tree and add node values to the result string separated by a delimiter, inserting N whenever we encounter a null node. During deserialization, we process the serialized string using an index i, create nodes for valid values, and return from the current path whenever we encounter N, reconstructing the tree accurately.

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Depth First Search

Intuition

We want to turn a tree into a string (serialize) and then rebuild the same tree from that string (deserialize).
We use preorder DFS (root → left → right) because it naturally records a node before its children.

When a node exists → record its value.
When a child is missing → record "N" so we know where null pointers are.

Example:
1,2,N,N,3,N,N uniquely represents a tree.

During deserialization, we read the list in order:

"N" → return None
Otherwise → create node, then build left, then right.

This works because preorder always visits nodes in the exact structure order.

Algorithm

Serialize

Use dfs preorder.
If node is null → append "N".
Else append node value.
Recursively process left child, then right child.
Join list with commas → return string.

Deserialize

Split string into list vals.
Use an index to process values in order.
If current value is "N" → return None.
Otherwise create a node.
Recursively build left subtree.
Recursively build right subtree.
Return the root.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Codec:

    # Encodes a tree to a single string.
    def serialize(self, root: Optional[TreeNode]) -> str:
        res = []

        def dfs(node):
            if not node:
                res.append("N")
                return
            res.append(str(node.val))
            dfs(node.left)
            dfs(node.right)

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

    # Decodes your encoded data to tree.
    def deserialize(self, data: str) -> Optional[TreeNode]:
        vals = data.split(",")
        self.i = 0

        def dfs():
            if vals[self.i] == "N":
                self.i += 1
                return None
            node = TreeNode(int(vals[self.i]))
            self.i += 1
            node.left = dfs()
            node.right = dfs()
            return node

        return dfs()

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

2. Breadth First Search

Intuition

Instead of using DFS, we treat the tree like a queue (level order traversal).
BFS visits nodes level by level, so we simply record values in that order:

If a node exists → record its value and push its children (even if they are None).
If a node is missing → record "N" to mark empty spots.

This ensures the structure is preserved, because BFS processes nodes exactly how they appear in the tree layout.

During deserialization, we again use BFS:

The first value is the root.
Then for each node in the queue, assign its left and right children from the next values in the list.

This keeps the tree reconstruction aligned with the serialized order.

Algorithm

Serialize

If root is None → return "N".
Initialize a queue with root.
While queue is not empty:
- Pop a node.
- If node exists → append its value, push left & right children.
- If node is missing → append "N".
Join the list with commas and return.

Deserialize

Split string into list vals.
If first value is "N" → return None.
Create root from first value and push it into a queue.
Use an index to read the next values:
- For each node popped from queue:
  - If vals[index] is not "N" → create left child & push.
  - Move index.
  - Repeat for right child.
Return the root of the rebuilt tree.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Codec:

    # Encodes a tree to a single string.
    def serialize(self, root: Optional[TreeNode]) -> str:
        if not root:
            return "N"
        res = []
        queue = deque([root])
        while queue:
            node = queue.popleft()
            if not node:
                res.append("N")
            else:
                res.append(str(node.val))
                queue.append(node.left)
                queue.append(node.right)
        return ",".join(res)

    # Decodes your encoded data to tree.
    def deserialize(self, data: str) -> Optional[TreeNode]:
        vals = data.split(",")
        if vals[0] == "N":
            return None
        root = TreeNode(int(vals[0]))
        queue = deque([root])
        index = 1
        while queue:
            node = queue.popleft()
            if vals[index] != "N":
                node.left = TreeNode(int(vals[index]))
                queue.append(node.left)
            index += 1
            if vals[index] != "N":
                node.right = TreeNode(int(vals[index]))
                queue.append(node.right)
            index += 1
        return root

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

Common Pitfalls

Forgetting to Handle Null Nodes

A common mistake is not encoding null children in the serialized string. Without explicit null markers (like "N"), the tree structure becomes ambiguous during deserialization. Two different trees could produce the same serialized string if nulls are omitted.

Using a Global Index Without Proper State Management

When deserializing with DFS, using a simple integer variable as an index fails because the index must persist across recursive calls. In many languages, primitive integers are passed by value, so the incremented index is lost when returning from recursion. The solution is to use a mutable wrapper (like an array or object) to maintain the index state.

Incorrect Order of Building Left and Right Subtrees

The deserialization must rebuild children in the exact same order they were serialized. If you serialize using preorder (root, left, right), you must deserialize in preorder too. Building the right subtree before the left will produce an incorrect tree structure.

Not Handling Empty Trees

An empty tree (null root) is a valid input that requires special handling. Forgetting to check for this case in both serialization and deserialization leads to null pointer exceptions or incorrect output.

Delimiter Conflicts with Node Values

Using a delimiter that could appear in node values causes parsing errors. For example, if nodes can have negative values and you use - as a delimiter, parsing becomes ambiguous. Using a character that cannot appear in integer values (like ,) avoids this issue.