Tree Serialization

Opening scenario

Problem references use LC for LeetCode.

Serialize and Deserialize Binary Tree (LC 297): design serialize(root) -> str and deserialize(str) -> root so that deserialize(serialize(t)) reproduces t exactly. Node values may repeat and may be negative; the tree is arbitrary (not a BST). Follow-up you should expect: do it so the serialized form is unambiguous with the fewest assumptions, and discuss BFS vs DFS encodings.

Reproducing a tree means preserving its shape and node values, not the identity of its node objects. The examples use integer-valued TreeNode objects with left and right fields, and deserialize strings produced by the matching serializer. Start by checking whether values alone tell you which children are missing.

Question progression

Q1 — Why isn't a single traversal (just preorder values) enough to rebuild the tree?

Question: If you write the preorder list of values, can you uniquely reconstruct the tree? If not, what is the missing information?