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 <= 1000root = [1,2,3,null,null,4,5]Output["1,2,#,#,3,4,#,#,5,#,#", reconstructed tree]WhyPreorder with null markers captures both values and missing children, so the reconstructed tree matches the original.root = []Output["#", null]WhyAn empty tree is represented by a single null marker and deserializes back to `None`.The number of nodes is in the range [0, 10^4]-1000 <= Node.val <= 1000The tree may be skewed or balancedSerialization must be deterministic and losslessdef serialize_deserialize(root):