Serialize a Tree
Trees & BST: lesson 12 of 14
Write the gaps down and the shape survives the trip.
Lesson 12 of 14 · 6 min
Serialize a Tree
Step 1 of 12
A tree has to survive a socket. Preorder gives a usable order — the # marks are what preserve the shape.
The Idea
A tree has to survive being written to a file or sent over a socket. Preorder gives the values in a usable order, and a marker for every absent child records the shape.
Rebuilding is the same walk in reverse: take the next token, then build the left subtree, then the right. The stream is read once, strictly forwards.
Real-World Example
Dictating a family tree over the phone. You name a person, then everything on their mother's side, then their father's — and you say "none" out loud, because silence would be ambiguous.
The Code
class Node:
def __init__(self, v, l=None, r=None): self.val, self.left, self.right = v, l, r
def dump(n): # preorder, with a mark for every gap
if not n: return ["#"]
return [str(n.val)] + dump(n.left) + dump(n.right)
def load(tokens):
t = tokens.pop(0) # the stream is read strictly in order
if t == "#": return None
return Node(int(t), load(tokens), load(tokens)) # left first, exactly as written
root = Node(1, Node(2), Node(3, Node(4), Node(5)))
text = ",".join(dump(root))
print(text) # 1,2,#,#,3,4,#,#,5,#,#
print(dump(load(text.split(","))) == dump(root)) # TrueYour turn
What does this print?
class Node:
def __init__(self, v, l=None, r=None): self.val, self.left, self.right = v, l, r
def dump(n):
if not n: return ["#"]
return [str(n.val)] + dump(n.left) + dump(n.right)
print(",".join(dump(Node(7, None, Node(8)))))Mini quiz
1 / 3