Serialize and deserialize a binary tree

Problem

Design two functions to serialize and deserialize a binary tree.

• Serialize : convert a binary tree into a single string.
• Deserialize : reconstruct the exact same binary tree from that string.

Assume the tree nodes are:

• val is an integer (may be negative)
• left / right pointers may be null

Requirements

1. deserialize(serialize(root)) must produce a tree structurally identical to root with the same node values.
2. Your format must handle:
   • empty tree
   • missing children (nulls) in arbitrary positions
   • large trees (e.g., up to ~10^5 nodes), so time and space complexity matter
3. Explain your chosen encoding format and analyze complexity.

Example

If the tree is:

• 1 as root
• left child 2
• right child 3 with children 4 and 5

Your serialized output could look like (format is up to you):

• "1,2,#,#,3,4,#,#,5,#,#"

where # indicates null.