In a Meta interview setting, implement a codec for a binary tree so a tree can be converted to a string and reconstructed exactly later. Your solution must preserve both node values and tree structure, including missing children.
You are given the root of a binary tree where each node has fields val, left, and right.
Implement two functions:
serialize(root) → returns a string representation of the tree.deserialize(data) → returns the root of the original binary tree reconstructed from that string.The deserialized tree must be structurally identical to the original tree and contain the same values.
Example 1
Input: root = [1,2,3,null,null,4,5]
Output: serialized string such as 1,2,#,#,3,4,#,#,5,#,#
Explanation: Using preorder traversal with null markers preserves the exact shape of the tree.
Example 2
Input: root = []
Output: #
Explanation: An empty tree should serialize to a null marker and deserialize back to None.
[0, 10^4]-1000 <= Node.val <= 1000