The machine must encode a binary tree into a string and later rebuild the identical tree from that string. The catch is that an in-order or pre-order list alone is ambiguous — many trees share the same traversal output.
The key insight is that a pre-order traversal that records null children removes all ambiguity. When the serialized stream includes None markers, the structure is fully recoverable: the stream becomes an exact blueprint of the tree, where each node is followed by its left subtree's stream and then its right subtree's stream.
The approach has three steps. First, serialize with a pre-order DFS: append the node's value, recurse left, recurse right, and append a null marker whenever a child is absent, joining values with a delimiter. Second, deserialize by splitting the string back into a list and walking it with a mutable index: read the next value; if it is the null marker, return None; otherwise build the node and recursively rebuild its left and right subtrees in the same pre-order. Third, return the rebuilt root. Each node appears exactly once in both passes, so time and space are O(n).
The trickiest edge case is the empty tree, which serializes to just a null marker and must deserialize back to None rather than crashing. The machine also depends on the index being shared across recursive calls — a new index per call would re-read the same values forever.
def serialize(root):
def dfs(node):
if not node:
return ["#"]
return [str(node.val)] + dfs(node.left) + dfs(node.right)
return ",".join(dfs(root))
def deserialize(data):
def dfs(vals):
v = next(vals)
if v == "#":
return None
node = TreeNode(int(v))
node.left = dfs(vals)
node.right = dfs(vals)
return node
return dfs(iter(data.split(",")))