LeetEye LeetEye
Medium Tree Traversal ~5 min

Serialize and Deserialize Binary Tree

trees serialize-and-deserialize-binary-tree

Problem

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.

Examples

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

Pre-order traversal with null markers creates a unique, reconstructable representation.

Pre-order with null markers: serialize by visiting root, left, right with 'null' for None. Deserialize by consuming values in same order, recursively building left then right.

How to Approach This Problem

Pattern Recognition: When you see keywords like serialize and deserialize binary tree trees, think Tree Traversal.

Step-by-Step Reasoning

1 Storing just values [1, 2, 3, 4, 5] fails because:
Answer: It doesn't capture tree structure
Same values can form different trees. We need structure info.
2 Including "null" for missing children helps because:
Answer: It marks where branches end
Without nulls, we can't tell where a subtree ends. Nulls are the "stop" signals.
3 Which traversals can uniquely serialize a tree with null markers?
Answer: Pre-order or level-order (both work)
Both work with null markers. In-order doesn't work because multiple trees can have the same in-order with nulls.
4 For tree [1, [2], [3, [4], [5]]], pre-order with nulls is:
Answer: 1, 2, null, null, 3, 4, null, null, 5, null, null
Visit 1, go left (2, null, null), go right (3, left (4, null, null), right (5, null, null)).
5 When deserializing pre-order, we:
Answer: Process values in order, recursively building left then right
First value is root. Then recursively build left subtree, then right subtree. Nulls signal "no child here."
6 When we encounter "null" during deserialization:
Answer: Return None and move to next value
Null means no node here. Return None, but continue processing remaining values.

Solution

class Codec:
    def serialize(self, root: TreeNode) -> str:
        result = []
        
        def preorder(node):
            if not node:
                result.append('N')
                return
            result.append(str(node.val))
            preorder(node.left)
            preorder(node.right)
        
        preorder(root)
        return ','.join(result)
    
    def deserialize(self, data: str) -> TreeNode:
        values = iter(data.split(','))
        
        def build():
            val = next(values)
            if val == 'N':
                return None
            node = TreeNode(int(val))
            node.left = build()
            node.right = build()
            return node
        
        return build()

Complexity Analysis

Time O(n)
Space O(n)

Master This Pattern

Build intuition with interactive MCQs. Practice Tree Traversal problems in the LeetEye app.

Download LeetEye Free
Practice in LeetEye