Serialize and Deserialize Binary Tree — LC 297 FAANG Hard

Problem Statement#

LeetCode 297 — Serialize and Deserialize Binary Tree | Difficulty: Hard

Design an algorithm to serialize a binary tree to a string and deserialize that string back to the original tree. There is no restriction on your format — just ensure encode and decode are inverses.

Constraints:

• The number of nodes is in the range [0, 10^4]
• -1000 <= Node.val <= 1000

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

Input:  root = []
Output: []

Why This Problem Matters#

Serialize/Deserialize Binary Tree is one of the most common hard problems at Facebook (Meta), Amazon, and Google. It tests system design thinking (how do you represent hierarchical data as a flat string?), tree traversal mastery, and the ability to write an encoder and decoder that are inverses of each other.

The problem appears in real systems — database query plan serialization, distributed computing job trees, and configuration file representation all use similar tree-to-string encodings. Understanding how preorder traversal with null markers uniquely encodes a binary tree (unlike inorder, which does not) is a key insight.

The Core Insight#

DFS Preorder approach: The preorder sequence (root → left → right) with explicit null markers uniquely identifies any binary tree. When deserializing, process the token stream left to right — each token is either a null (no node) or a value (create a node and recursively build its left then right subtree).

Why preorder works but inorder does not: Inorder traversal alone cannot uniquely reconstruct an arbitrary binary tree without knowing root positions. Preorder always processes the root first, which anchors the reconstruction.

BFS level-order approach: More intuitive (matches LeetCode's display format), but the deserializer needs a queue to pair parents with their children.

Visual Dry Run#

Tree: [1, 2, 3, null, null, 4, 5]

Preorder DFS serialization:

• Visit 1: emit "1,"
• Visit 2: emit "2,"
• Visit null (left of 2): emit "#,"
• Visit null (right of 2): emit "#,"
• Visit 3: emit "3,"
• Visit 4: emit "4,"
• Visit null, null (4's children): emit "#,#,"
• Visit 5: emit "5,"
• Visit null, null (5's children): emit "#,#,"

Serialized: "1,2,#,#,3,4,#,#,5,#,#"

Deserialization: read left to right, build root first then children recursively.

Solution (Optimal)#

class Codec:
    def serialize(self, root) -> str:
        def dfs(node):
            if not node:
                return ['#']
            return [str(node.val)] + dfs(node.left) + dfs(node.right)
        return ','.join(dfs(root))
 
    def deserialize(self, data: str):
        vals = iter(data.split(','))
 
        def build():
            val = next(vals)
            if val == '#':
                return None
            node = TreeNode(int(val))
            node.left = build()
            node.right = build()
            return node
 
        return build()

var serialize = function(root) {
    function dfs(node) {
        if (!node) return '#,';
        return node.val + ',' + dfs(node.left) + dfs(node.right);
    }
    return dfs(root);
};
 
var deserialize = function(data) {
    const vals = data.split(',');
    let idx = 0;
 
    function build() {
        if (vals[idx] === '#') {
            idx++;
            return null;
        }
        const node = new TreeNode(parseInt(vals[idx++]));
        node.left = build();
        node.right = build();
        return node;
    }
 
    return build();
};

Time: O(n) for both serialize and deserialize — each node visited once Space: O(n) — output string is O(n); recursion stack is O(h)

Common Mistakes#

• Using inorder traversal — inorder does not uniquely reconstruct an arbitrary binary tree
• Forgetting null markers — without them, you cannot tell where one subtree ends and another begins
• Using a mutable index in Python deserializer — Python integers are immutable; use a list ([0]), a closure variable with nonlocal, or an iterator (iter())
• Splitting on comma without handling empty strings — watch for trailing commas that produce empty tokens
• Not handling the empty tree case — serialize should return an empty string or just "#", and deserialize should return null

Interview Tips#

• State both DFS preorder and BFS level-order approaches — interviewers appreciate seeing multiple solutions
• Explain why preorder uniquely encodes a tree while inorder does not
• The Python iter() trick for the shared index pointer is clean and worth explaining
• Mention that this pattern (tree to flat format with null markers) is used in real systems like LeetCode's own input format

Follow-up Questions#

• How would you serialize an n-ary tree? Include a child count at each node (or use a special "end of children" marker) along with null markers.
• What if node values can contain commas? Use a different delimiter or encode values with length-prefixing.
• What is the minimum length serialization? You can omit trailing nulls in BFS to save space; DFS preorder is already fairly compact.
• Can you serialize without null markers if you have both preorder and inorder? Yes — preorder + inorder uniquely reconstructs any binary tree without null markers (LC 105).
• How does this differ for BSTs? BSTs only need preorder (no null markers) because the BST property determines which side each value goes (LC 1008).

Key Takeaways#

• DFS preorder with null markers uniquely encodes any binary tree — root comes first, then left subtree, then right
• Deserializing preorder: read tokens left to right, build root then recursively build left and right children
• Null markers (like "#") are essential — they tell the deserializer when a subtree is empty
• A shared index/iterator across recursive calls is the key implementation challenge in deserialize
• Inorder traversal alone cannot uniquely reconstruct a binary tree — only preorder or postorder with null markers can
• Time O(n), space O(n) — both proportional to the number of nodes
• This serialize/deserialize pattern is used in real distributed systems, databases, and compilers for tree representations