DSA · Trees · #161
Serialize and Deserialize Binary Tree
Module 44 · difficulty 4/5·⏱ 30:00starts on first keystroke
Design an algorithm to serialize a binary tree to a string and deserialize that string back into the original tree structure. Implement a `Codec` class with two methods: - `serialize(root)` — encodes a binary tree to a single string. - `deserialize(data)` — decodes the string produced by `serialize` back into the identical tree. The specific encoding format is up to you, but `deserialize(serialize(root))` MUST reconstruct a tree identical in structure and node values to the original. Each tree node is `{ val, left, right }` with `left`/`right` being a node or `null`.
Examples
root = [1,2,3,null,null,4,5]→[1,2,3,null,null,4,5]— serialize then deserialize yields a tree identical to the input.root = []→[]— An empty tree round-trips to an empty tree.root = [1,2]→[1,2]— A node may have only a left child.
Constraints
- · The number of nodes in the tree is in the range [0, 10^4].
- · -1000 <= Node.val <= 1000
- · serialize and deserialize must be inverses: deserialize(serialize(root)) reconstructs the tree.
- · You may choose any internal string format.
Session phases
A · Clarify
B · Approach
C · Complexity
D · Edges
E · Code
F · Tradeoff
G · Score
Phase A — Clarify
Ask questions about input bounds, types, and edge constraints.
Ask the coach clarifying questions about the problem.
When you've covered this phase, advance to the next.