Practice: Serialize a Tree
Tree to string and back.
To save a tree to a file, or send it over a network, we need to turn it into a string. And then rebuild the exact same tree from that string. That's serializing and deserializing.

- Save or send a tree
- Turn it into a string
- Rebuild the same tree
Preorder with markers
We write the tree in preorder, root, left, right, and write a hash mark for every empty child. Those markers make the string unambiguous. To rebuild, we read the values back in the same order, with an iterator. Run it. The rebuilt tree gives the same string.
from tree import sample, TreeNode
def serialize(node):
if not node:
return "#"
return f"{node.value},{serialize(node.left)},{serialize(node.right)}"
def deserialize(text):
vals = iter(text.split(","))
def build():
v = next(vals)
if v == "#":
return None
return TreeNode(int(v), build(), build())
return build()
s = serialize(sample())
print(s)
print(serialize(deserialize(s)) == s)8,3,1,#,#,6,4,#,#,7,#,#,10,#,14,13,#,#,# True
Also uses tree.py
class TreeNode:
def __init__(self, value, left=None, right=None):
self.value, self.left, self.right = value, left, right
def sample():
return TreeNode(8,
TreeNode(3, TreeNode(1), TreeNode(6, TreeNode(4), TreeNode(7))),
TreeNode(10, None, TreeNode(14, TreeNode(13))))
PICTURE = ' 8\n / \\\n 3 10\n / \\ \\\n 1 6 14\n / \\ /\n 4 7 13'Why the markers
Without the empty markers, different trees could give the same string, and we couldn't rebuild the right one. With them, preorder alone is enough. Both directions visit every node once, so they're O of N. The same idea is used when programs save complex data to files.
| key | value |
|---|---|
| Order | root, left, right |
| # | an empty child |
| Rebuild | same order, an iterator |
| Cost | O(n) both ways |
Summary
Serialize a tree in preorder with empty markers, and rebuild it by reading in the same order. Next, common interview questions.
Key takeaways- Preorder
- Mark empty children
- Rebuild with an iterator