Serialize and Deserialize Binary Tree

Design functions that turn a binary tree into a string and rebuild exactly the same tree from that string.

A way to picture it

You're shipping a bonsai tree through the post, flat-packed. You write assembly instructions while walking the tree: each branch's value, and a '#' wherever a branch is missing. The receiver follows the same walk and rebuilds it exactly.

How to approach it

Preorder with '#' for nulls. The markers pin down the shape, so deserialization can read the tokens back in the same order, recursively.

Example

Input: {"root":[1,2,3,null,null,4,5]}. Output: [1,2,3,null,null,4,5].

Complexity: O(n) time and O(n) space. Each node and each null marker is written and read once.

This page includes an animated walkthrough, Java and Python solutions, and a question to check your understanding.