Serialize and Deserialize Binary Tree

Problem

Design a codec that converts a binary tree to a string and back. serialize(root) must produce a string, and deserialize(data) must rebuild a tree with exactly the same shape and values from that string. You may choose any format as long as the round trip is exact; you are not required to match any particular encoding. The tree may be empty.

• The tree has at most 15,000 nodes.
• Node values are integers between -1,500 and 1,500.

Examples

• root = [9, 3, 20, None, None, 15, 7] → serializing produces "9,3,20,#,#,15,7,#,#,#,#", and deserializing that string rebuilds a tree whose level-order form is [9, 3, 20, None, None, 15, 7].
• root = [] → serializing the empty tree gives "", and deserializing "" gives back None.
• root = [42] → a single node serializes to "42,#,#" and round-trips to [42].

Hints

1. Why can you not rebuild a tree from a plain preorder list of values? What is missing?
2. If you write an explicit marker every time a child is absent, does one traversal become enough?
3. Level-order (BFS) with a null marker per missing child, values separated by a delimiter; deserialize with the same queue discipline, consuming two tokens per real node.