49. Serialize and Deserialize Binary Tree

You’re interviewing for a backend role at a FAANG-level company where systems exchange data across services (microservices), regions (multi-datacenter), and even devices (offline-first clients).

The interviewer explains a production challenge:

A platform needs to transmit and store binary trees that represent real structures such as:

• feature-flag rollout decision trees
• recommendation rule trees
• indexing and query-planning trees
• permissions and entitlement trees
• service routing and failover trees

Because these trees must move across networks and be saved in logs, caches, queues, or databases, the platform must convert a tree into a compact string format (serialization), and later rebuild the exact same tree from that string (deserialization).

If the encoding is wrong or incomplete, the receiving system may reconstruct an incorrect tree, causing bad routing, incorrect authorization, wrong recommendations, or production outages.

This is a classic hard interview problem that tests your ability to design a robust encoding scheme and correctly rebuild recursive structures, often asked in Google, Amazon, Netflix, Meta, Apple, Microsoft, Uber, and Bloomberg interviews.

Your Task

Design an algorithm to:

• serialize a binary tree to a string
• deserialize that string back to the original binary tree

You must ensure that deserializing the serialized output produces a tree that is structurally identical and has the same node values as the original tree.

Input Format

root: the root node of a binary tree

Each node is defined as:

TreeNode { int val; TreeNode left; TreeNode right; }

Output Format

Return an object / implementation with two functions:

• serialize(root) -> string
• deserialize(data) -> TreeNode

Examples

Constraints

• 0 <= number of nodes <= 100,000
• -10^9 <= Node.val <= 10^9
• Tree can be highly unbalanced (worst-case like a linked list)
• Serialization must include enough information to reconstruct null children