AI Hints
Home›DSA in Python Tutorial›More Practice: Sets, Windows and Trees
DSA in Python · Lesson 126 of 132

Practice: Serialize a Tree

Tree to string and back.

⏱ 2 min read▶ Video at 2:29:50🎓 Free
Watch this lesson in the DSA in Python courseWatch on YouTube ↗Full DSA in Python course

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.

Practice: Serialize a Tree
From the video: Practice: Serialize a Tree
  • 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.

serialize.pypython
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)
Output
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.

keyvalue
Orderroot, left, right
#an empty child
Rebuildsame order, an iterator
CostO(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
Next up: Interview Questions: Part 1 — the questions they ask