Serialize and Deserialize Binary Tree
Problem statement
Design a class Codec with two methods:
serialize(root)turns a binary tree of integers into a string.deserialize(data)turns such a string back into a tree with exactly the same shape and values.
The string format is entirely up to you. The only requirement is that deserialize(serialize(root)) rebuilds the original tree, including empty trees, negative values and trees that lean entirely to one side. Node values are not unique, so you can't rely on them to identify nodes.
In the examples, trees are written in level order, left to right, with null for a missing child and trailing nulls dropped.
Examples
Example 1
Input: root = [8,3,10,null,6,null,14]
Output: [8, 3, 10, null, 6, null, 14]
Explanation: The round trip gives back the same tree. With the preorder format below, the string in between is 8,3,#,6,#,#,10,#,14,#,#.
Example 2
Input: root = []
Output: []
Explanation: An empty tree must survive too. The preorder format stores it as #.
Hints
Approach
Preorder DFS with null markers. Serialise recursively: for None write #; otherwise write the value, then serialise the left subtree, then the right. Join the tokens with commas.
Deserialise by reading the same tokens in the same order from an iterator. build() takes the next token: # means None; anything else becomes a node whose left child is build() and whose right child is the following build(). Because every missing child was written down, each token's position tells you exactly where it belongs, so no indices or queue are needed.
Every node and every null marker is written and read once. The recursion depth equals the tree height, which can be n for a skewed tree, so very deep trees would need an explicit stack.
O(n)Space O(n)from collections import deque class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right class Codec: def serialize(self, root): out = [] def walk(node): if node is None: out.append("#") return out.append(str(node.val)) walk(node.left) walk(node.right) walk(root) return ",".join(out) def deserialize(self, data): tokens = iter(data.split(",")) def build(): tok = next(tokens) if tok == "#": return None node = TreeNode(int(tok)) node.left = build() node.right = build() return node return build() # Demo: build the example tree, round-trip it, print it level by level.def to_list(root): out, queue = [], deque([root]) while queue: node = queue.popleft() out.append(node.val if node else None) if node: queue.extend([node.left, node.right]) while out and out[-1] is None: out.pop() return out codec = Codec()root = TreeNode(8, TreeNode(3, None, TreeNode(6)), TreeNode(10, None, TreeNode(14)))print(to_list(codec.deserialize(codec.serialize(root))))print(to_list(codec.deserialize(codec.serialize(None))))Follow-up questions
- Serialise an N-ary tree, where each node has any number of children. (Write the child count after each value.)
- Make both directions iterative so that a tree with a million nodes in a single chain doesn't overflow the call stack.
Frequently asked questions
Serialisation is how state crosses process and machine boundaries: snapshots, RPC payloads, caches, anything written to disk and read back later. This problem tests whether you can design a format that round-trips exactly and handles edge cases (empty input, negative numbers, skewed shapes) without being told how.
Many different trees share the same preorder list; for example, a root with one child could have it on the left or the right. Recording null children removes the ambiguity. Without markers you need two traversals (preorder plus inorder) and unique values, which this problem doesn't promise.
Use a binary encoding instead of decimal text, or store a bitmask per node saying which children exist instead of writing # markers. For a binary search tree, preorder alone is enough, because the value ordering determines the shape.