#297 Serialize and Deserialize Binary Tree

frequently reported atLinkedIn Microsoft ByteDance / TikTok Uber Amazon NVIDIA

the problem

In plain words

Design a Codec with serialize(root) → String and deserialize(data) → root, such that deserialize(serialize(tree)) rebuilds the same tree. One Codec object may write and a different one read. The format is up to you.

in root = [1,2,3,null,null,4,5]

out [1,2,3,null,null,4,5]

Any string format works as long as the round trip is exact.

in root = []

out []

0 ≤ number of nodes ≤ 10⁴
-1000 ≤ Node.val ≤ 1000

your turn

Try it before you peek

Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.

Solve it in the browser

Design: implement every operation. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.

Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.

Marking the problem solved, or opening every hint, also shows it.

the aha

Key insight

patternBuild a tree from traversals Tree BFS (level order)

where this runsLeetCode's own tree notation, like [1,null,2], is level order with null markers — the BFS codec on this page.

One traversal is ambiguous — unless you also write down the nulls. With null markers, a preorder string pins the tree down exactly, and the reader rebuilds it in the same order it was written.

solutions

From brute force to optimal

Write nodes level by level, "#" for a missing child; read them back two at a time per parent.

BFS that also queues nulls (LinkedList) and writes "#".
Deserialize: queue of parents; each parent consumes the next two tokens as its children.

timeO(n)

Each node and null marker is written and read once.

spaceO(n)

The string, the token array and the queue — and no recursion, so deep trees are safe.

javaclass Codec (BFS)java.util.*

1class Codec {2    /** Level order, "#" for a missing child: "1,2,3,#,#,4,5,#,#,#,#". */3    public String serialize(TreeNode root) {4        if (root == null) return "";5        StringBuilder sb = new StringBuilder();6        Queue<TreeNode> queue = new LinkedList<>();   // LinkedList allows null; ArrayDeque does not7        queue.offer(root);8        while (!queue.isEmpty()) {9            TreeNode node = queue.poll();10            if (node == null) { sb.append("#,"); continue; }11            sb.append(node.val).append(',');12            queue.offer(node.left);13            queue.offer(node.right);14        }15        return sb.toString();16    }17 18    public TreeNode deserialize(String data) {19        if (data.isEmpty()) return null;20        String[] tokens = data.split(",");21        TreeNode root = new TreeNode(Integer.parseInt(tokens[0]));22        Deque<TreeNode> parents = new ArrayDeque<>();23        parents.offer(root);24        int i = 1;25        while (!parents.isEmpty()) {          // tokens come in pairs: left child, right child26            TreeNode parent = parents.poll();27            if (!tokens[i].equals("#")) {28                parent.left = new TreeNode(Integer.parseInt(tokens[i]));29                parents.offer(parent.left);30            }31            i++;32            if (!tokens[i].equals("#")) {33                parent.right = new TreeNode(Integer.parseInt(tokens[i]));34                parents.offer(parent.right);35            }36            i++;37        }38        return root;39    }40}

Write root, left, right recursively with "#" for null; read tokens back in the same order.

serialize: null → "#,"; else value, then left, then right.
deserialize: poll a token; "#" → null; else make a node, build its left, then its right.

timeO(n)

Each node and each of the n + 1 nulls is handled once.

spaceO(n)

The string and token deque; the recursion is O(h).

javaclass Codec (preorder)java.util.*

1class Codec {2    /** Preorder, "#" for null: "1,2,#,#,3,4,#,#,5,#,#". */3    public String serialize(TreeNode root) {4        StringBuilder sb = new StringBuilder();5        write(root, sb);6        return sb.toString();7    }8 9    private void write(TreeNode node, StringBuilder sb) {10        if (node == null) { sb.append("#,"); return; }11        sb.append(node.val).append(',');12        write(node.left, sb);13        write(node.right, sb);14    }15 16    public TreeNode deserialize(String data) {17        Deque<String> tokens = new ArrayDeque<>(Arrays.asList(data.split(",")));18        return read(tokens);19    }20 21    /** Consumes exactly one subtree's worth of tokens, in the same order they were written. */22    private TreeNode read(Deque<String> tokens) {23        String token = tokens.poll();24        if (token.equals("#")) return null;25        TreeNode node = new TreeNode(Integer.parseInt(token));26        node.left = read(tokens);27        node.right = read(tokens);28        return node;29    }30}

sim

Dry run

loading simulation…

javajava.util.*

1class Codec {2    /** Preorder, "#" for null: "1,2,#,#,3,4,#,#,5,#,#". */3    public String serialize(TreeNode root) {4        StringBuilder sb = new StringBuilder();5        write(root, sb);6        return sb.toString();7    }8 9    private void write(TreeNode node, StringBuilder sb) {10        if (node == null) { sb.append("#,"); return; }11        sb.append(node.val).append(',');12        write(node.left, sb);13        write(node.right, sb);14    }15 16    public TreeNode deserialize(String data) {17        Deque<String> tokens = new ArrayDeque<>(Arrays.asList(data.split(",")));18        return read(tokens);19    }20 21    /** Consumes exactly one subtree's worth of tokens, in the same order they were written. */22    private TreeNode read(Deque<String> tokens) {23        String token = tokens.poll();24        if (token.equals("#")) return null;25        TreeNode node = new TreeNode(Integer.parseInt(token));26        node.left = read(tokens);27        node.right = read(tokens);28        return node;29    }30}

in the room

How to say it in the interview

talk track

State the format first and show it on the example tree: "1,2,#,#,3,4,#,#,5,#,#,".
Explain why null markers make one traversal enough.
Mention the recursion-depth risk for skewed trees and that the BFS codec avoids it.

traps

Forgetting separators: 1 and 23 vs 12 and 3.
Using ArrayDeque to queue null children — it throws.
Building a String with += in a loop: O(n²). Use StringBuilder.
Keeping the tree in a field instead of really encoding it — a different Codec object does the reading.

what they ask next

Follow-ups

Serialize and Deserialize BST (LC 449)?

Preorder without null markers is enough: the BST ordering tells you where each value goes (rebuild with value bounds).

Make it compact?

Write values as fixed-width binary (4 bytes each) plus a bitmap for nulls instead of text.

before you submit

Edge cases to test

Empty tree → serialize to a marker, and deserialize it back to null.
Negative and multi-digit values: "-1000," must not merge with its neighbours.
A deep chain: the recursive codec is as deep as the tree — the BFS codec has no recursion at all.

practise next