295. Serialize and Deserialize Binary Tree

Problem¶

Serialize a binary tree into a string, then deserialize that string back into the exact same tree.

Example:

tree:    1
        / \
       2   3
          / \
         4   5

serialize(tree) -> some string
deserialize(that string) -> same tree structure and values

Key trick¶

Use a traversal that keeps None children.

Without null markers, different trees can serialize to the same data.
Preorder is the simplest:
- write node.val
- then left subtree
- then right subtree
- write a marker like "null" for missing children

Trap¶

Common mistakes:

Omitting null children, which loses structure.
Using level-order but trimming nulls incorrectly, so deserialization is ambiguous.
Building recursively without considering deep skewed trees.
Returning a Python object/list instead of a string.

Why is it interesting?¶

It tests tree fundamentals plus interface design.

You must preserve both:
- values
- shape
It also shows whether you can choose a representation and invert it cleanly.

Python solution¶

from utils import TreeNode


class Solution:
    def serialize(self, root):
        # Preorder traversal with null markers preserves full tree structure.
        vals = []

        def dfs(node):
            if node is None:
                vals.append("null")
                return
            vals.append(str(node.val))
            dfs(node.left)
            dfs(node.right)

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

    def deserialize(self, data):
        # Read the preorder stream in the same order it was written.
        vals = iter(data.split(","))

        def dfs():
            val = next(vals)
            if val == "null":
                return None
            node = TreeNode(int(val))
            node.left = dfs()
            node.right = dfs()
            return node

        return dfs()

Complexity:

Serialize: \(O(n)\)
Deserialize: \(O(n)\)
Extra space: \(O(n)\)

Comment on my solution¶

Your solution is correct and nicely symmetric.

Good points:

Very readable.
Structure is preserved exactly.
json.dumps and json.loads make the format safe and simple.

Main weakness:

It stores each node as nested lists, which is more verbose than needed.

Interview note:

A plain preorder string with null markers is more standard and shows the serialization logic directly.
Your recursive approach can also hit recursion depth on a very skewed tree near \(10^4\) nodes.

## Solution

from utils import TreeNode
import json

# Works
class Codec:

    def serialize(self, root):
        """Encodes a tree to a single string.

        :type root: TreeNode
        :rtype: str
        """
        def to_list(node):
            if node is None:
                return None
            return [node.val, to_list(node.left), to_list(node.right)]

        return json.dumps(to_list(root))

    def deserialize(self, data):
        """Decodes your encoded data to tree.

        :type data: str
        :rtype: TreeNode
        """
        def to_tree(tree_list):
            if tree_list is None:
                return None
            node = TreeNode(tree_list[0])
            node.left = to_tree(tree_list[1])
            node.right = to_tree(tree_list[2])
            return node
        return to_tree(json.loads(data))

Codec().serialize(Codec().deserialize("[1,[2, null, null],[3, null, null]]"))