Turn a binary tree into a string and back. Write it in preorder with a marker for every missing child, then read it back the same way.
▼The problem
LeetCode 297 (Hard). Design an algorithm to serialize a binary tree to a string and deserialize that string back to the original tree structure. Any format works, as long as deserialize(serialize(root)) gives back the same tree.
Examples (LeetCode's): root = [1,2,3,null,null,4,5] round-trips to [1,2,3,null,null,4,5], and root = [] to [].
The solution
def serialize(root):
if not root:
return '#'
left = serialize(root.left)
right = serialize(root.right)
return f'{root.val},{left},{right}'
def deserialize(data):
tokens = iter(data.split(','))
def build():
tok = next(tokens)
if tok == '#':
return None
node = TreeNode(int(tok))
node.left = build()
node.right = build()
return node
return build()Transcript
Serialize and Deserialize Binary Tree. Turn a binary tree into a string, then turn that string back into the very same tree.
Take this tree: one on top, children two and three, and three has children four and five. Unpacked, every node must land in the same place, and an empty tree must survive too.
The easy way: write just the values, in preorder: one, two, three. But a chain, three under two under one, writes one, two, three too. Values alone lose the shape.
The fix: write the gaps too. Picture threading beads on a string. Walk in preorder: the node, then its left side, then its right. Each value is a bead; each missing child is a black hash bead. Now the two trees give different strings.
In code, serialize returns a hash for None, else the value, then left, then right. To deserialize, split on commas and read tokens with an iterator: a hash means None, otherwise make a node, build its left, then its right.
Our tree threads as one, two, hash, hash, three, four, hash, hash, five, hash, hash. Now unthread it. One is the root. Two hangs left; two hashes close it. Three hangs right, then four and five, each closed by two hashes. Same tree. An empty tree is one hash.
Every node and every gap is written once and read once: order n time and order n space, both ways. LeetCode's own format, level order with a queue, works too.
Thread, mark the gaps, rebuild. That's Serialize and Deserialize Binary Tree.