Serialize and deserialize a binary tree (Staff+ schema extension)

Expected question

"Serialize a binary tree to a string and deserialize the string back to the same tree."

Variant forms

• "Serialize and deserialize a binary tree using preorder traversal."
• "Use level-order encoding instead — what changes?"
• "How do you prove null children are represented unambiguously?"
• "Stream a very large tree without materializing its full serialized form."
• "Add a schema version so the format can evolve safely."
• "Reject malformed or truncated input rather than silently accepting it."
• "What if callers pass a graph with cycles instead of a tree?"
• "How would you make the wire format compact and language-independent?"

The question, as it might actually be asked

Implement serialize(root) -> str and deserialize(data) -> TreeNode | None for a binary tree. The reconstructed tree must have the same values and shape, including missing children.

How you'd talk while coding

I'd clarify value types, empty-tree marker, whether the format must stay stable, and how malformed input fails. Brute "store object refs" only works in-process. Correct is preorder with explicit nulls — encode and decode consume tokens in the same order. I'd prefix a schema version. Tests: empty v1,#; one-sided child; negatives; truncated/trailing/bad version raise. Staff+ stop line: "Treat the string as an API — version, validate exact consumption, bound depth for untrusted payloads. Cycles mean it's a graph codec, not a tree codec. I stop there unless they want streaming I/O."

Where this actually gets asked

Backend / infra interviews. Tests recursive invariants, parser discipline, wire-format trade-offs. Staff follow-ups treat serialized data as a versioned, validated API.

Problem

Serialize a binary tree into a deterministic string and deserialize it into an equivalent tree. Values are integers for the reference implementation.

Clarifying questions you should ask first

1. Are node values integers, strings with escaping needs, or arbitrary objects?
2. Must the output be deterministic and backward compatible?
3. Which malformed inputs should be rejected?
4. Can the input be very deep or large enough to require iterative/streaming traversal?
5. Is the input guaranteed to be a tree, or must we detect shared nodes/cycles?

Approach ladder

Reference solution (Python)

from __future__ import annotations

from dataclasses import dataclass
from typing import Iterator


@dataclass
class TreeNode:
    value: int
    left: "TreeNode | None" = None
    right: "TreeNode | None" = None


class Codec:
    _VERSION = "v1"
    _NULL = "#"

    def serialize(self, root: TreeNode | None) -> str:
        seen: set[int] = set()

        def encode(node: TreeNode | None) -> Iterator[str]:
            if node is None:
                yield self._NULL
                return
            identity = id(node)
            if identity in seen:
                raise ValueError("input contains a cycle or shared node")
            seen.add(identity)
            yield str(node.value)
            yield from encode(node.left)
            yield from encode(node.right)

        return ",".join([self._VERSION, *encode(root)])

    def deserialize(self, data: str) -> TreeNode | None:
        tokens = iter(data.split(","))
        if next(tokens, None) != self._VERSION:
            raise ValueError("unsupported or missing schema version")

        def decode() -> TreeNode | None:
            try:
                token = next(tokens)
            except StopIteration as error:
                raise ValueError("truncated tree payload") from error
            if token == self._NULL:
                return None
            try:
                value = int(token)
            except ValueError as error:
                raise ValueError(f"invalid node value: {token!r}") from error
            return TreeNode(value, decode(), decode())

        root = decode()
        if next(tokens, None) is not None:
            raise ValueError("payload contains trailing tokens")
        return root

Complexity: serialization and deserialization are O(n) time and O(n) output/auxiliary space; recursive call-stack depth is O(height).

Tests / edge cases

1. Empty tree serializes to v1,# and deserializes to None.
2. A node with only one child preserves which side is absent.
3. Negative and multi-digit values round trip correctly.
4. Truncated, trailing, invalid-value, and unknown-version payloads fail explicitly.
5. A cyclic or shared-node object graph is rejected instead of causing nontermination or ambiguous tree output.

Staff+ deep dive

What's expected at each level

• Mid-level: Includes null markers and reconstructs shape correctly.
• Senior: Produces symmetric traversal code and tests asymmetric trees.
• Staff+: Defines a stable wire contract, validation behavior, and limits for untrusted or large input.
• Principal: Connects schema ownership to migration rollout, cross-language compatibility, and operational observability.

Follow-up questions to expect

• "Use BFS?" — Include nulls in level order; trim trailing nulls only by a documented rule.
• "Values are strings?" — Length-prefix or an escaping grammar — comma-split alone breaks.
• "Huge tree?" — Iterative traversal, streaming I/O, explicit size/depth limits.

Related

• 07-graph-clone-and-cycle-safe.md
• 06-merge-k-sorted-iterators.md
• 00-staff-plus-coding-bar.md