Coding Interview: Serialize and Deserialize a Binary Tree

Problem and Applicable Context

Implement two functions for an arbitrary binary tree:

• serialize(root) converts the tree into a string.
• deserialize(data) reconstructs a tree with the same values and shape.

Assume node values are signed 32-bit integers, the tree may be empty, and the serialized string only needs to interoperate with this decoder. For the recursive interview implementation, assume the tree height fits the language's call-stack limit. The decoder below also rejects malformed text rather than silently accepting a partial tree.

For this tree:

1
       / \
      2   3
         / \
        4   5

the chosen format is:

1,2,#,#,3,4,#,#,5,#,#

Each integer records a node, # records a missing child, commas separate tokens, and preorder determines how tokens are consumed. Public material updated in 2026 presents this exact problem with preorder and level-order solutions, while an interviewing.io replay shows it being asked in a mock interview with a Meta engineer. That supports it as a current representative coding exercise without claiming that every company or interview uses it.

What the Interviewer Is Evaluating

The first signal is whether the candidate defines reversibility before choosing a traversal. Preorder values alone are insufficient. A root 1 with left child 2 and a root 1 with right child 2 both produce [1, 2] unless missing children are encoded. Their marked forms differ:

Left child:  1,2,#,#,#
Right child: 1,#,2,#,#

The second signal is designing encoder and decoder as inverses. In preorder, a decoder reads one token. # completes an empty subtree. A value starts a node, after which the next complete subtree belongs to the left child and the following complete subtree belongs to the right child. The format therefore supplies its own recursive boundaries without storing subtree lengths.

The third signal is a real correctness argument. For a tree with n nodes, there are n + 1 null child pointers, so the encoding contains exactly 2n + 1 tokens. More importantly, the decoder must consume exactly the tokens for one subtree and leave the iterator positioned at the next subtree. Structural induction proves that property.

Finally, the interviewer looks for engineering boundaries: invalid input, negative and duplicate values, recursion depth, output size, and when BFS or a production serialization format is the better choice.

Clarifying Questions Before Answering

• Is this an arbitrary binary tree or a binary search tree? An arbitrary tree needs structural

markers. A BST can sometimes be reconstructed from preorder plus an explicit duplicate policy.

• Must the string follow an existing wire format? This prompt permits a private format.

Cross-service storage needs schema versioning, compatibility rules, and often a standard codec.

• Can node values contain the delimiter or sentinel? They are integers, so comma and # are

unambiguous. General strings would need escaping or length prefixes.

• Can the tree be empty? Yes. It serializes to #.
• Can input be extremely deep or adversarial? The recursive answer assumes bounded height.

Untrusted or deeply skewed trees require an explicit stack and resource limits.

• Will deserialize receive only trusted output from serialize? The code remains strict:

empty text, invalid integers, truncated trees, and trailing tokens are rejected.

• Do we optimize for readability or minimum bytes? Preorder text is easy to explain and test.

A compact binary protocol would encode tags and integers differently.

30-Second Answer Framework

“I will use preorder traversal and emit # for every missing child. A value token means create a node, then recursively decode its left and right subtrees; # means return None. Null markers are required because values alone cannot distinguish a left child from a right child. The encoder and decoder mirror each other, and structural induction shows that each decode call consumes exactly one subtree. Both operations take O(n) time and produce O(n) data, with O(h) call stack for height h. I will also reject truncated or trailing input and mention an iterative BFS or stack-based version when depth is unbounded.”

Step-by-Step Deep Dive

Step one: reject the values-only baseline with a counterexample.

Preorder, inorder, or postorder values do not uniquely identify an arbitrary binary tree by themselves. Even combining preorder and inorder becomes ambiguous when duplicate values are allowed. The format must encode shape as well as values. A null marker is the simplest shape signal for an interview string format.

Step two: choose a grammar that can be decoded from left to right.

The format can be described recursively:

tree := "#"
      | integer "," tree "," tree

The actual implementation tokenizes on commas first, so each recursive call consumes one token and, for a value, two following subtree encodings. Signed integer text never contains , or #. An empty tree is #; a leaf with value 7 is 7,#,#.

This grammar also gives a useful counting invariant. A binary tree with n real nodes has n + 1 null child pointers. Serialization therefore emits n value tokens and n + 1 null tokens, for 2n + 1 tokens total. The count is a diagnostic, not a substitute for parsing: malformed tokens can still have an odd total.

Step three: implement the mirrored recursive operations.

from __future__ import annotations

from dataclasses import dataclass


MIN_INT32 = -(2**31)
MAX_INT32 = 2**31 - 1


@dataclass
class TreeNode:
    val: int
    left: TreeNode | None = None
    right: TreeNode | None = None


class Codec:
    NULL = "#"
    SEP = ","

    def serialize(self, root: TreeNode | None) -> str:
        tokens: list[str] = []

        def visit(node: TreeNode | None) -> None:
            if node is None:
                tokens.append(self.NULL)
                return

            if node.val < MIN_INT32 or node.val > MAX_INT32:
                raise ValueError("node value is outside signed 32-bit range")

            tokens.append(str(node.val))
            visit(node.left)
            visit(node.right)

        visit(root)
        return self.SEP.join(tokens)

    def deserialize(self, data: str) -> TreeNode | None:
        if data == "":
            raise ValueError("serialization cannot be empty")

        tokens = iter(data.split(self.SEP))

        def build() -> TreeNode | None:
            try:
                token = next(tokens)
            except StopIteration:
                raise ValueError("serialization is truncated") from None

            if token == self.NULL:
                return None

            try:
                value = int(token)
            except ValueError:
                raise ValueError(f"invalid integer token: {token}") from None

            if value < MIN_INT32 or value > MAX_INT32:
                raise ValueError("node value is outside signed 32-bit range")

            node = TreeNode(value)
            node.left = build()
            node.right = build()
            return node

        root = build()

        try:
            extra = next(tokens)
        except StopIteration:
            return root

        raise ValueError(f"trailing token: {extra}")

Building a token list avoids repeated string concatenation during serialization. The decoder shares one iterator among recursive calls, so a child does not restart at the beginning. Checking for a remaining token after the root is complete prevents valid-prefix input such as 1,#,#,9,#,# from being accepted.

Step four: prove that decoding reverses serialization.

Use structural induction on a tree T.

• Base case: if T is empty, serialization emits #. The decoder reads #, returns None, and

consumes exactly that subtree's one token.

• Inductive step: suppose the claim holds for the left and right subtrees. Serialization emits

the root value, followed by the complete left encoding, then the complete right encoding. The decoder creates the same root, the first recursive call consumes exactly the left encoding by the hypothesis, and the second consumes exactly the right encoding. It reconstructs the same shape and values and stops immediately after T.

Thus deserialize(serialize(T)) is structurally equal to T, and each call leaves the iterator at the next unread subtree. The final trailing-token check verifies that the root consumed the whole input.

Step five: calculate cost without hiding the output or stack.

Both operations visit each real node and null pointer once, so time is O(n). The serialized output and tokenized input are O(n). The reconstructed tree itself is also O(n). Recursive call-stack usage is O(h), where h is tree height: O(log n) for a balanced tree and O(n) for a fully skewed tree.

The recursive code is a good interview answer when height is bounded and clarity matters. It is not safe for an attacker-controlled chain longer than the runtime recursion limit. In that case, use an explicit stack or level-order queue and enforce maximum node, token, byte, and depth limits.

Step six: compare preorder DFS with level-order BFS.

Both can be reversible in O(n) time and output space if they retain null information.

BFS is preferable when recursion depth is the immediate risk or the surrounding system already uses a level-order representation. Preorder is preferable for the base interview because its grammar and proof are smaller.

Step seven: verify round trips and malformed input.

Round-trip tests should cover:

Also reject "", 1,#, x,#,#, 2147483648,#,#, and 1,#,#,2,#,#. For generated trees, compare the original and decoded trees recursively and assert serialize(deserialize(serialize(root))) == serialize(root). A skewed-tree test should run near the accepted height boundary so the stack assumption is visible rather than accidental.

High-Quality Sample Answer

“I would first confirm that this is an arbitrary binary tree, values are signed 32-bit integers, and the format only needs to be read by our decoder. Because duplicate values are allowed, I need to encode structure explicitly.

I will traverse in preorder. For a real node I emit its value, then its left and right subtrees; for a missing child I emit #. This distinguishes, for example, a left child from a right child even when the preorder values are identical. During decoding, one shared token iterator mirrors the same grammar: # returns None; otherwise I create a node and recursively build left then right.

Correctness follows by structural induction. The empty tree is one #. For a real root, assuming each recursive call reconstructs and consumes exactly one child subtree, the two calls consume the serialized left and right parts in order and rebuild the original root. I will reject premature end, invalid or out-of-range values, and trailing tokens.

Each real node and null pointer is processed once, so both operations are O(n). The text and tokens use O(n) space, while recursion uses O(h) stack. If tree height can be adversarial, I would switch to an explicit stack or BFS and impose size and depth limits. I would test empty, single-node, left-only versus right-only, duplicates, negative values, integer bounds, malformed strings, and randomized round trips.”

Common Mistakes

• Serialize only node values → different shapes can produce the same traversal → **emit null

markers or another explicit structural boundary.**

• Use a delimiter that can appear inside values → token boundaries become ambiguous → **escape

values, add lengths, or choose a delimiter outside the value grammar.**

• Create a new iterator in every recursive call → each child rereads the first token →

share one advancing iterator or index.

• Decode the root and ignore remaining text → a valid prefix hides corrupt trailing data →

require complete input consumption.

• Let a missing token surface as an unrelated exception → truncated data is hard to diagnose →

convert premature exhaustion into a clear parse error.

• Claim auxiliary space is always O(log n) → a skewed tree has height n, and tokenization

also uses linear space → separate output, token storage, tree, and call-stack costs.

• Call preorder values sufficient for a BST without defining duplicates → equal keys can make

reconstruction ambiguous → state the ordering and duplicate policy before removing markers.

• Use recursive code for untrusted depth without limits → a long chain can exhaust the stack →

use an explicit stack and resource bounds.

• Compare object identity after a round trip → reconstruction creates new nodes → **compare

values and structure.**

• Test only a balanced example → left/right ambiguity and stack risk remain hidden → **include

empty, one-sided, duplicate, extreme, malformed, and skewed cases.**

Follow-Up Questions and Responses

Follow-up 1: Can a binary search tree omit null markers?

Often yes. With a strict BST invariant and unique keys, preorder can be reconstructed by carrying lower and upper bounds: values inside the current range belong to that subtree, and the first value outside it belongs to an ancestor. If duplicates are allowed, the contract must say whether equal values go left, right, or are counted in the node. Without that policy, the compact format is ambiguous. The arbitrary-tree base problem cannot use this optimization.

Follow-up 2: How would you support arbitrary string values?

Comma and # may occur inside a string, so delimiter splitting is no longer self-delimiting. One option is a length prefix such as 5:hello, followed by explicit node/null tags. Another is a standard serialization library with a schema. Escaping can work, but the decoder must distinguish escaped separators from structural separators and handle invalid escape sequences. Length prefixes make consumption rules easier to prove.

Follow-up 3: What changes for a tree with millions of nodes or extreme depth?

Avoid recursive calls and avoid splitting the entire input if peak memory matters. Stream tokens through an iterative parser with an explicit stack of child slots, and stream output to a writer instead of collecting all tokens first. Enforce maximum bytes, tokens, nodes, integer length, and depth before allocating unbounded state. Time remains O(n), but memory follows the active stack or queue plus the output buffer policy.

Follow-up 4: How would you version this format in a production system?

Add a format identifier and version outside the tree payload, define integer width and text encoding, and specify whether unknown fields or versions fail closed. Include an integrity check when corruption must be detected, but do not treat a checksum as authentication. Rollouts need read-old/write-new compatibility and fixtures for every supported version. For cross-language services, a maintained schema-based format is usually safer than extending the interview codec.

Follow-up 5: Could level-order serialization safely trim trailing nulls?

Yes, if the decoder defines omitted positions after the last real node as null and the serializer trims only the final run of null markers. It must not remove an internal null because that changes the child alignment of later nodes. The round-trip contract and malformed-input rules should be tested after trimming; “looks like a shorter array” is not a proof of equivalence.