Design an algorithm to serialize and deserialize a binary tree.
This problem follows the Pre-order + Null Markers pattern, commonly found in the Trees category. Recognizing this pattern is key to solving it efficiently in an interview setting.
Pre-order traversal with null markers. Deserialize by consuming tokens in order.
Pre-order + null markers uniquely define a tree — the null markers tell you exactly when to stop recursing and return up.
def serialize(root):
if not root: return '#'
return str(root.val) + ',' + serialize(root.left) + ',' + serialize(root.right)
def deserialize(data):
tokens = iter(data.split(','))
def build():
val = next(tokens)
if val == '#': return null
node = TreeNode(int(val))
node.left = build()
node.right = build()
return node
return build()Practice Serialize and Deserialize Binary Tree and similar Trees problems with flashcards. Build pattern recognition through active recall.
Practice this problem