Serialize and Deserialize a Binary Tree

Problem Design an algorithm to serialize a binary tree to a string, and deserialize that string back into an identical tree. Any encoding format is allowed, as long as serialize and deserialize are inverses.

Input / Output

• Input (serialize): the root of a binary tree.
• Output (serialize): a string. deserialize consumes that string and returns the reconstructed root.

Constraints

• Up to 10^4 nodes; node values may be negative.
• The tree may be arbitrarily shaped (skewed, complete, or empty).

Example

• [1,2,3,null,null,4,5] → some string → the same tree structure and values.
• An empty tree must round-trip correctly.