Problem 34

Serialize and Restore a Saved Navigation Tree

HARDDESIGN

Tree+3

You're persisting users' saved navigation trees — folders, sub-folders, bookmarks — into flat strings so they can be stored as a single blob and replayed later.

Write serialize(root) that turns a binary tree into a string, and deserialize(data) that rebuilds the original tree from that string. The judge does not check your encoding format — it checks the round trip: for every test tree, deserialize(serialize(tree)) must produce an identical tree.

You pick the format. Anything goes — preorder + null markers, level-order BFS with a delimiter, JSON, your own scheme — as long as the round trip is exact.

Requirements

Implement serialize(root) taking a TreeNode | None and returning a str.
Implement deserialize(data) taking the string produced by serialize and returning a TreeNode | None.
An empty tree (None) must round-trip cleanly: deserialize(serialize(None)) returns None.
Structure must be preserved, not just values. Trees with the same values arranged differently must serialize to different strings.
Do not modify the provided TreeNode class. Tests construct trees by hand and rely on its shape.

Examples

Example 1

Input

Output

deserialize(serialize(root)) reproduces the same five-node tree (structurally identical).

Example 2

Input

Left-leaning chain: 1 → 2 (left) → 3 (left) → 4 (left)

Output

Round trip preserves the chain — none of the nodes get duplicated into the right side.

Example 3

Input

       1
      / \
     2   2     (duplicate values at different positions)

Output

After round trip, the two `2` nodes are still distinct children of `1`.

Constraints

serialize and deserialize must be inverses for any binary tree the tests pass in.
Use only the standard library (json is fine if you want it).
Treat the encoding as opaque — tests only call serialize and deserialize, never inspect the string itself.

Follow-up

How would you handle very large trees that can't be loaded into a single string in memory? What changes about the encoding?

Hints

Related Practice

Track

Algorithms & Data Structures

Keep moving through related algorithms & data structures problems and build a stronger search-friendly practice loop around this topic.

View track →

Problem 25

Build a User Action Rate Limiter

easy

Problem 31