Serialize and Deserialize Binary Tree

HardBinary Tree · Design (DFS / BFS)🧩 Tree DFS LeetCode #297 ↗Updated Oct 30, 2026

Problem

Design a Codec: serialize(root) turns a binary tree (possibly empty) into a string, deserialize(data) rebuilds the identical tree. Any format is fine.

Input[1,2,3,null,null,4,5]Outputsame tree

Input[]Output[]

0 ≤ n ≤ 10⁴ · -1000 ≤ Node.val ≤ 1000 · codec must be stateless

Try it yourself

Java

class Codec {
    public String serialize(TreeNode root) {
        
    }

    public TreeNode deserialize(String data) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

A traversal that also records null children (#) fixes the shape; replay it to rebuild.

PatternTree DFS

Instinct If the answer for a node can be built from the answers of its left and right subtrees, write one recursive function and trust it on the children.

Memory hack Ask the kids, then decide - each child reports up, the parent combines, and a global variable keeps the best "bend" seen so far.

Open the Tree DFS guide →

Approaches

Brute ForceHeap-Indexed Array (Complete-Tree Slots)

Time O(2^h)Space O(2^h)

Heap layout: slot i has children 2i+1, 2i+2. Write all 2^h-1 slots (# = empty); a skewed tree wastes almost all of them.

Java

class Codec {
    public String serialize(TreeNode root) {
        String[] slots = new String[(1 << height(root)) - 1];
        Arrays.fill(slots, "#");
        fill(root, 0, slots);
        return String.join(",", slots);
    }
    private int height(TreeNode t) {
        return t == null ? 0 : 1 + Math.max(height(t.left), height(t.right));
    }
    private void fill(TreeNode t, int i, String[] s) {
        if (t == null) return;
        s[i] = String.valueOf(t.val);
        fill(t.left, 2 * i + 1, s); fill(t.right, 2 * i + 2, s);
    }
    public TreeNode deserialize(String data) {
        return data.isEmpty() ? null : build(data.split(","), 0);
    }
    private TreeNode build(String[] s, int i) {
        if (i >= s.length || s[i].equals("#")) return null;
        return new TreeNode(Integer.parseInt(s[i]), build(s, 2 * i + 1), build(s, 2 * i + 2));
    }
}

Fine for balanced trees; explodes (and overflows int indices) on deep ones.

BetterBFS Level Order with Null Markers

Time O(n)Space O(n)

BFS writes each value and a # per missing child (2n+1 tokens); to rebuild, each queued parent takes the next two tokens.

Java

class Codec {
    public String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        Queue<TreeNode> q = new LinkedList<>(Arrays.asList(root)); // allows nulls
        while (!q.isEmpty()) {
            TreeNode n = q.poll();
            sb.append(n == null ? "#" : n.val).append(',');
            if (n != null) { q.add(n.left); q.add(n.right); }
        }
        return sb.toString();
    }
    public TreeNode deserialize(String data) {
        String[] s = data.split(",");
        if (s[0].equals("#")) return null;
        TreeNode root = new TreeNode(Integer.parseInt(s[0]));
        Queue<TreeNode> q = new ArrayDeque<>(List.of(root));
        for (int i = 1; !q.isEmpty(); i += 2) { // each parent reads 2 tokens
            TreeNode n = q.poll();
            if (!s[i].equals("#")) q.add(n.left = new TreeNode(Integer.parseInt(s[i])));
            if (!s[i+1].equals("#")) q.add(n.right = new TreeNode(Integer.parseInt(s[i+1])));
        }
        return root;
    }
}

Linear and recursion-free (LeetCode's own format), but needs queues and an index.

OptimalDFS Preorder with Null Markers

Time O(n)Space O(n)

Write value, left subtree, right subtree (# for null). Reading mirrors it: take a token; # → null, else make a node and read its left, then right subtree. Both functions have the same shape.

Java

class Codec {
    public String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        write(root, sb);
        return sb.toString();
    }
    private void write(TreeNode t, StringBuilder sb) {
        if (t == null) { sb.append("#,"); return; }
        sb.append(t.val).append(',');
        write(t.left, sb); write(t.right, sb);
    }
    public TreeNode deserialize(String data) {
        return read(new ArrayDeque<>(Arrays.asList(data.split(","))));
    }
    private TreeNode read(Deque<String> tokens) {
        String tok = tokens.poll();
        if (tok.equals("#")) return null;
        TreeNode t = new TreeNode(Integer.parseInt(tok));
        t.left = read(tokens); // left subtree's tokens come first
        t.right = read(tokens);
        return t;
    }
}

Linear, compact and symmetric; recursion depth is O(h).

Pro tip

For a BST (LC 449) the null markers can go: preorder plus value bounds alone determine the shape.

At a glance

Level	Approach	Time	Space
Brute Force	Heap-Indexed Array (Complete-Tree Slots)	`O(2^h)`	`O(2^h)`
Better	BFS Level Order with Null Markers	`O(n)`	`O(n)`
Optimal	DFS Preorder with Null Markers	`O(n)`	`O(n)`

Common pitfalls

No null markers — 1,2 can't say which child 2 is.
No separator — 12 could be one node or two.
s += ... in a loop is O(n²); use StringBuilder.

Interview tips

Ask about value range and size — they drive the format.
Explain why it is unambiguous: 2n+1 tokens, nulls included.
Offer BFS to avoid deep recursion on skewed trees.

Pattern

Traversal with null sentinels → encode tree shape losslessly; decode by replaying the traversal.

My notes saved in this browser