Serialize and Deserialize Binary Tree
Convert a binary tree to a string and reconstruct the identical structure.
Why does this pattern fit?
Restate the exact job
Convert a binary tree to a string and reconstruct the identical structure.
Null markers make traversal shape unambiguous.
O(n) time · O(n) space
Omitting null markers makes different shapes share one encoding.
How to solve Serialize and Deserialize Binary Tree
The goal is to solve this problem from the pattern, not to memorize a finished answer. Use this as a check after your own attempt.
What the question asks
Convert a binary tree to a string and reconstruct the identical structure.
Why Trees & recursive traversal fits
Null markers make traversal shape unambiguous.
State to maintain
A preorder token stream with explicit nulls and a read index.
Transition
Serialize node,left,right; deserialize by consuming one token recursively.
Time and space
O(n) time · O(n) space
Counterexample to the tempting mistake
Omitting null markers makes different shapes share one encoding.
Prove it again tomorrow
Close this page. Rebuild the state and transition from memory, write a test that exposes the mistake above, then solve a fresh input without looking back. A same-day reread is practice, not proof of retention.