Serialize and Deserialize Binary Tree

Design a Codec class that turns a binary tree into a string and back:

• serialize(root) takes the root of a binary tree and returns a string that encodes it.
• deserialize(data) takes a string produced by serialize and returns the root of the tree it encodes.

The format is entirely up to you. The only requirement is that the round trip is exact: deserialize(serialize(root)) must rebuild a tree with the same shape and the same values as root. The grader never inspects the string itself; it calls serialize, then passes the string to deserialize on a fresh Codec instance and compares the rebuilt tree with the original. So the string must carry all the information: do not keep the tree in instance, class, or global variables.

Values can be negative and can repeat, and the tree can be empty.

In the examples, root is written in level order (null marks a missing child), and the output is the tree that your deserialize must return.