Serialize and Deserialize Binary Tree

Problem Design an algorithm to serialize a binary tree into a string and deserialize that string back into the identical tree. No restriction on the format — it only needs to round-trip.

Input / Output

• serialize: root → string; deserialize: string → root.

Constraints

• Up to 10^4 nodes; values may be negative and multi-digit (delimiters matter).

Example

• Tree [1,2,3,null,null,4,5] → "1,2,#,#,3,4,#,#,5,#,#" (preorder with null markers) → same tree.

Expected approach

• Preorder DFS emitting a sentinel (e.g. "#") for null children; deserialize by consuming tokens recursively — the null markers make the preorder unambiguous. O(n) time and space both ways. BFS level-order with null markers works equally well. Be ready to discuss why plain inorder/preorder without markers is insufficient for arbitrary (non-BST) trees.