Problem

In a Meta interview setting, you may need to send a binary tree between services used by products like Messenger or Instagram. Implement two functions: one to serialize a binary tree into a string, and one to deserialize that string back into the original tree.

Your encoding must preserve both node values and tree structure exactly. Different trees must not produce the same serialized output.

Formal Specification

• Input to serialize(root): the root node of a binary tree, or null
• Output of serialize(root): a string
• Input to deserialize(data): a string produced by serialize
• Output of deserialize(data): the reconstructed root node, or null

Use the following node shape:

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

A valid solution should run in linear time relative to the number of nodes.

Examples

Example 1 Input: root = [1,2,3,null,null,4,5] Output: serialized = "1,2,#,#,3,4,#,#,5,#,#" Explanation: Preorder traversal with # markers preserves missing children.

Example 2 Input: root = [] Output: serialized = "#" Explanation: An empty tree must still be represented explicitly.

Constraints

• 0 <= number of nodes <= 10^4
• -1000 <= Node.val <= 1000
• The tree may be unbalanced
• The input to deserialize is guaranteed to come from serialize