LeetCode 297 Serialize and Deserialize Binary Tree: Preorder, BFS and the BST Variant

LeetCode 297 asks you to design a codec: one function turns a binary tree into a string, the other turns that string back into an identical tree. It is tagged Hard, but the core idea fits in one sentence. The difficulty lives in the details: choosing the traversal, encoding nulls, parsing tokens without off-by-one bugs, and explaining why your format is unambiguous. This guide builds the idea from first principles, codes both standard approaches, then shows the BST shortcut that interviewers ask about next.

The Problem: Design a Codec for Any Binary Tree

Implement two methods:

• serialize(root) returns a string.
• deserialize(data) takes that string and returns the root of a tree with the same structure and values.

There is no required format. Your only constraint is that deserialize(serialize(root)) reproduces the original tree. LeetCode's constraints: up to 10⁴ nodes, values in [-1000, 1000]. Note the negative values; any encoding that assumes non-negative single digits will fail.

The freedom to choose a format is the real test. Interviewers want to see you reason about what information a string must carry to identify a tree uniquely. That reasoning starts with a classic fact.

Why One Traversal Is Not Enough, and Why Nulls Fix It

You might remember that you need two traversals, such as preorder plus inorder, to rebuild a binary tree (LeetCode 105). That is true when you record only the values. Consider these two trees:

Without nulls, the preorder sequences collide. With a marker for every missing child, they differ. In general, preorder-with-nulls is a complete description of the tree: every node announces its value, and every position where a subtree could start tells you whether one does.

Why does this work for preorder but not inorder? In preorder, when you read a token you always know which position it fills: it is the root of the subtree you are currently building. The decoder makes the same decisions in the same order as the encoder. Inorder with nulls is still ambiguous: the tree 2 with left child 1 and the tree 1 with right child 2 both produce # 1 # 2 #, because the root sits in the middle and you cannot tell where it is. Preorder and postorder with nulls are unambiguous; BFS with nulls is unambiguous too.

Approach 1: Preorder DFS With Null Markers

Serialize: visit the node, write its value, recurse left, recurse right. On null, write #. Join with commas.

Deserialize: split the string into tokens. Read the next token. If it is #, return null. Otherwise create a node, then build its left subtree from the following tokens, then its right subtree. The key engineering detail is that every recursive call must consume tokens from the same shared position. Use an iterator (Python), an index field (Java), or pass an index by reference (C++).

import java.util.*;

class TreeNode {
    int val; TreeNode left, right;
    TreeNode(int x) { val = x; }
}

public class Codec {
    private static final String NULL = "#";
    private static final String SEP = ",";

    public String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        build(root, sb);
        return sb.toString();
    }

    private void build(TreeNode node, StringBuilder sb) {
        if (node == null) {
            sb.append(NULL).append(SEP);
            return;
        }
        sb.append(node.val).append(SEP);
        build(node.left, sb);
        build(node.right, sb);
    }

    public TreeNode deserialize(String data) {
        Deque<String> tokens = new ArrayDeque<>(Arrays.asList(data.split(SEP)));
        return parse(tokens);
    }

    private TreeNode parse(Deque<String> tokens) {
        String t = tokens.poll();
        if (t.equals(NULL)) return null;
        TreeNode node = new TreeNode(Integer.parseInt(t));
        node.left = parse(tokens);
        node.right = parse(tokens);
        return node;
    }
}

Two Java details. String.split(",") drops trailing empty strings, so the trailing comma after the last token is harmless. And ArrayDeque.poll() is O(1), whereas repeatedly calling list.remove(0) on an ArrayList would make decoding O(n²).

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Codec:
    def serialize(self, root):
        out = []
        def dfs(node):
            if node is None:
                out.append("#")
                return
            out.append(str(node.val))
            dfs(node.left)
            dfs(node.right)
        dfs(root)
        return ",".join(out)

    def deserialize(self, data):
        tokens = iter(data.split(","))
        def build():
            t = next(tokens)
            if t == "#":
                return None
            node = TreeNode(int(t))
            node.left = build()
            node.right = build()
            return node
        return build()

The Python iterator is the cleanest way to share position across recursive calls: each next(tokens) advances the same cursor. If you prefer an index, wrap it in a list or use nonlocal; a plain integer parameter would be copied and every call would re-read the same token.

Complexity: O(n) time for both directions (2n + 1 tokens, constant work each). O(n) space for the string and token list, plus O(h) recursion depth, where h is between log n and n.

Dry Run: Encoding and Decoding a Five-Node Tree

Serialize (preorder, writing # for each null):

1. Visit 1, write 1. Go left.
2. Visit 2, write 2. Its left is null: #. Its right is null: #.
3. Back to 1, go right. Visit 3, write 3.
4. Visit 4: 4,#,#. Visit 5: 5,#,#.

Result: 1,2,#,#,3,4,#,#,5,#,#. Five nodes, 11 tokens, which matches 2n + 1.

Deserialize, tracking the token index:

The decoder never needs to look ahead. Each token's position is determined by the tokens already read. That property, every prefix telling you exactly where the next token goes, is what makes the format unambiguous.

Approach 2: BFS Level-Order Encoding

This is the format LeetCode uses when it shows you a tree like [1,2,3,null,null,4,5]. Serialize with a queue: pop a node, write its value (or # for null), and push both children of every non-null node, even if they are null.

Deserialize with a queue of parents waiting for children. The first token is the root. Then tokens come in pairs: the next two tokens are the left and right children of the parent at the front of the queue. Each non-null child is pushed so it can receive its own children later.

#include <string>
#include <sstream>
#include <queue>
using namespace std;

struct TreeNode {
    int val; TreeNode *left, *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Codec {
public:
    string serialize(TreeNode* root) {
        if (!root) return "";
        string out;
        queue<TreeNode*> q;
        q.push(root);
        while (!q.empty()) {
            TreeNode* node = q.front(); q.pop();
            if (!node) { out += "#,"; continue; }
            out += to_string(node->val) + ",";
            q.push(node->left);
            q.push(node->right);
        }
        return out;
    }

    TreeNode* deserialize(const string& data) {
        if (data.empty()) return nullptr;
        stringstream ss(data);
        string tok;
        getline(ss, tok, ',');
        TreeNode* root = new TreeNode(stoi(tok));
        queue<TreeNode*> parents;
        parents.push(root);
        while (!parents.empty()) {
            TreeNode* p = parents.front(); parents.pop();
            if (getline(ss, tok, ',') && tok != "#") {
                p->left = new TreeNode(stoi(tok));
                parents.push(p->left);
            }
            if (getline(ss, tok, ',') && tok != "#") {
                p->right = new TreeNode(stoi(tok));
                parents.push(p->right);
            }
        }
        return root;
    }
};

from collections import deque

class CodecBFS:
    def serialize(self, root):
        if not root:
            return ""
        out, q = [], deque([root])
        while q:
            node = q.popleft()
            if node is None:
                out.append("#")
                continue
            out.append(str(node.val))
            q.append(node.left)
            q.append(node.right)
        while out and out[-1] == "#":   # optional: trim trailing nulls
            out.pop()
        return ",".join(out)

    def deserialize(self, data):
        if not data:
            return None
        tokens = data.split(",")
        root = TreeNode(int(tokens[0]))
        parents, i = deque([root]), 1
        while parents and i < len(tokens):
            p = parents.popleft()
            if i < len(tokens) and tokens[i] != "#":
                p.left = TreeNode(int(tokens[i]))
                parents.append(p.left)
            i += 1
            if i < len(tokens) and tokens[i] != "#":
                p.right = TreeNode(int(tokens[i]))
                parents.append(p.right)
            i += 1
        return root

The Python version trims trailing # tokens, exactly like LeetCode's display format. The decoder handles that by treating "ran out of tokens" as null. Trimming saves roughly half the null tokens for a complete tree, because the last level's children are all null.

Dry run on the same tree: serialize produces 1,2,3,#,#,4,5,#,#,#,#, which trims to 1,2,3,#,#,4,5. Decode: root 1. Parent 1 takes 2 and 3. Parent 2 takes #, #. Parent 3 takes 4, 5. Parents 4 and 5 find no tokens left, so their children are null. Done.

Complexity: O(n) time both ways. Space O(n) for output and O(w) for the queue, where w is the maximum level width (up to about n/2 for a complete tree). No recursion, so skewed trees are safe.

The BST Variant: LeetCode 449 Without Null Markers

LeetCode 449, Serialize and Deserialize BST, adds one requirement: the encoded string should be as compact as possible. Because a BST orders its values, you can drop the null markers entirely and send only the preorder values.

Why does that work? In a BST, the inorder traversal is just the sorted values. So preorder plus "sort it to get inorder" gives you the two traversals needed to rebuild a tree. Better still, you do not have to sort: you can decode directly from preorder using bounds. Read the next value. If it lies within (low, high) it belongs here: create the node, build its left subtree with bounds (low, value) and its right subtree with bounds (value, high). If it lies outside, this subtree is empty; return null without consuming the token.

public class BstCodec {
    public String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        pre(root, sb);
        return sb.length() == 0 ? "" : sb.substring(0, sb.length() - 1);
    }

    private void pre(TreeNode n, StringBuilder sb) {
        if (n == null) return;
        sb.append(n.val).append(',');
        pre(n.left, sb);
        pre(n.right, sb);
    }

    private int idx;
    private int[] vals;

    public TreeNode deserialize(String data) {
        if (data.isEmpty()) return null;
        String[] parts = data.split(",");
        vals = new int[parts.length];
        for (int i = 0; i < parts.length; i++) vals[i] = Integer.parseInt(parts[i]);
        idx = 0;
        return build(Long.MIN_VALUE, Long.MAX_VALUE);
    }

    private TreeNode build(long low, long high) {
        if (idx == vals.length) return null;
        int v = vals[idx];
        if (v < low || v > high) return null;
        idx++;
        TreeNode node = new TreeNode(v);
        node.left = build(low, v);
        node.right = build(v, high);
        return node;
    }
}

class BstCodec:
    def serialize(self, root):
        out = []
        def pre(n):
            if n:
                out.append(str(n.val))
                pre(n.left)
                pre(n.right)
        pre(root)
        return ",".join(out)

    def deserialize(self, data):
        if not data:
            return None
        vals = list(map(int, data.split(",")))
        i = 0
        def build(low, high):
            nonlocal i
            if i == len(vals) or not (low <= vals[i] <= high):
                return None
            v = vals[i]
            i += 1
            node = TreeNode(v)
            node.left = build(low, v)
            node.right = build(v, high)
            return node
        return build(float("-inf"), float("inf"))

LeetCode 449 guarantees distinct values. If a BST could contain duplicates, you would need a convention (for example "duplicates go left") and matching bounds. Ask the interviewer. Each value is consumed exactly once and each failed bound check returns immediately, so decoding is O(n), not the O(n log n) of the sort-and-rebuild approach.

Making it even smaller

LC 449's "as compact as possible" invites further ideas. Decimal text uses up to 5 characters per value plus a comma. You could write each value as fixed-width bytes (4 bytes for any 32-bit int) or a variable-length encoding where small numbers take one byte. In an interview, describe this as an option and explain the trade-off: smaller payload, but the string is no longer human-readable and needs careful decoding. For a refresher on BST properties that make all of this possible, see binary search tree interview problems.

DFS vs BFS vs BST Encoding: Which to Use

My recommendation for interviews: lead with preorder DFS. It is about 20 lines, the proof of correctness is one sentence ("the decoder reads tokens in the exact order the encoder wrote them"), and the code mirrors itself. Mention BFS as the alternative if recursion depth is a concern. Bring up the BST variant only if asked, or as a smart aside if the interviewer says the tree is a BST.

Pitfalls and Edge Cases

• Empty tree. DFS serialize gives #, which decodes to null correctly. BFS returns an empty string; make sure deserialize checks for it before calling stoi or int().
• Negative and multi-digit values. -1000 is five characters. Always delimit tokens. A format like "one char per node" fails immediately.
• Null token collides with a value. If you choose N or # you are safe for integer trees. If node values were arbitrary strings, you would need escaping or length-prefixing (for example 3:abc). Interviewers sometimes ask this to check your design thinking.
• Quadratic decoding. Removing from the front of a Python list or Java ArrayList is O(n) per removal, so decoding becomes O(n²). Use an iterator, an index, or a deque.
• Integer parameter for position. Passing i by value into recursive calls is the most common bug. Every call reads the same token and the tree comes out wrong.
• Global state across calls. If you store the index as a field (as in the Java BST codec), reset it at the start of each deserialize. LeetCode reuses codec objects across test cases.
• Not testing round-trips. The simplest test is serialize(deserialize(serialize(t))) == serialize(t) on a handful of trees: empty, single node, left-skewed, right-skewed, complete.

How Interviewers Use This Problem, and Follow-Ups to Expect

This question tests three things at once: recursion fluency, the ability to design a format and argue it is unambiguous, and careful handling of string parsing. A strong answer states the format first, explains why nulls are needed with the two-tree counterexample, codes serialize and deserialize as mirror images, and then dry-runs a small tree.

Common follow-up questions

• "Why do you need the null markers?" Show Tree A and Tree B above. Same preorder values, different shapes.
• "What if it's a BST?" Drop the nulls and decode with bounds. O(n).
• "What if it's an N-ary tree?" (LeetCode 428.) Write each node's value followed by its child count, then recurse on each child. Or write a value then its children followed by an end marker. Same principle: the decoder must always know where the next token goes.
• "How would you serialize a graph with cycles?" Assign IDs to nodes, write a node list and an edge list, and use a visited map so shared nodes are written once. Pure tree traversal would loop forever.
• "How would you check if two trees are identical, or if one is a subtree of another?" Serialize both with null markers and compare strings, or search for one string inside the other (LeetCode 572). The null markers are what make the substring check correct. Delimit carefully so that value 2 does not match inside 12; wrap each token, for example ,2,.
• "Find duplicate subtrees." (LeetCode 652.) Serialize every subtree in postorder and count the strings in a hash map. This is the same encoding used as a hash key.
• "Where is this used in real systems?" Saving tree-shaped data to disk or sending it over a network: JSON and Protocol Buffers for nested objects, a database index persisted to pages, a trie snapshot, the DOM sent from server to browser.

That last answer is optional, but it connects the problem to engineering and is a nice signal for SDE-2 and above candidates. If tree recursion still feels shaky, work through recursion for beginners and the patterns in binary tree interview problems first. Another tree classic that pairs well with this one is LeetCode 236 Lowest Common Ancestor, which uses the same "what does each node return to its parent" thinking. For BFS mechanics in general, see graph BFS and DFS problems.

A 12-minute plan for the interview

1. Clarify (1 min). Value range, negatives, empty tree, is it a BST, any size constraint on the output?
2. Design the format (2 min). Preorder with # for nulls, comma separated. Show why nulls are needed.
3. Code serialize (2 min). Five lines of recursion.
4. Code deserialize (3 min). Mirror of serialize with a shared cursor. Call out the shared-cursor detail explicitly.
5. Dry run (2 min). A three to five node tree with at least one missing child.
6. Complexity and alternatives (2 min). O(n) both ways; BFS avoids recursion depth; BST drops nulls.

Frequently Asked Questions

Pranjal Jain

Ex-Microsoft SDE · IIT Kanpur · Founder of Prepflix. Helps engineers crack startup and product company interviews across India.