Serialize and Deserialize Binary Tree
Design two functions: one that converts a binary tree into a string, and one that rebuilds an identical tree from that string. The format is up to you; the pair must round-trip any tree, including ones with null children in arbitrary positions.
- 0 ≤ number of nodes ≤ 10^4
- -1000 ≤ node value ≤ 1000
- A single traversal order is ambiguous unless nulls are recorded
- Pre-order with explicit null markers is uniquely decodable
- Deserialization consumes tokens in the same order they were produced
Nearly every tree problem is a traversal with the right information passed down (bounds, depth) or returned up (height, best path through this node). Inorder on a BST yields sorted order, which solves kth-smallest and validation; BFS with a queue yields levels.
Serialize with a pre-order traversal that emits each value followed by its left and right subtrees, writing # for a null child. Deserialize by reading tokens in order: a # returns null, otherwise create the node and recursively build its left then right child from the following tokens. Because nulls are explicit, the token stream describes the structure unambiguously and no separate in-order sequence is needed.
- Level-order with null markers also works and is what LeetCode's display format uses; it needs a queue instead of recursion. Storing pre-order plus in-order works only for unique values.