The problem
Design serialize (turn a binary tree into a string) and deserialize (turn that string back into the same tree).
Input: [1, 2, 3, null, null, 4, 5] Serialized: "1,2,#,#,3,4,#,#,5,#,#" Output: the same tree, rebuilt
Picture it
Picture packing a tree into a parcel tape. Walk it in preorder (node, left, right) and write each value onto the tape. Whenever there is an empty spot, write #, so the shape travels too. To unpack, read the tape from the start: a value creates a node and then builds its left and right from the following tokens; a # means “nothing here”.
How to recognise it
- You must turn a tree into flat text and back again, with nothing lost: same values, same shape.
- A traversal alone loses the shape (different trees share a preorder), so the text must also record where the empty spots are.
- With empty spots marked, one preorder list (node, left, right) is enough: reading it back is the same recursion in reverse.
- Up to 10^4 nodes, values from −1000 to 1000, so negative numbers must survive the round trip.
Start with brute force
Store the tree like a heap array: the root at position 0 and the children of position i at 2i + 1 and 2i + 2. Write # for every unused position up to the last node.
def serialize_brute(root):
slots = {}
def place(node, i): # heap positions: children of i are 2i+1, 2i+2
if node:
slots[i] = node.val
place(node.left, 2 * i + 1)
place(node.right, 2 * i + 2)
place(root, 0)
size = max(slots, default=-1) + 1
return ",".join(str(slots[i]) if i in slots else "#" for i in range(size))
This is simple, and reading it back only needs the same position arithmetic. But the length depends on the height, not the number of nodes: a right-leaning chain of n nodes needs 2^n − 1 slots. With 20 nodes that is already about 10^6 slots; with 10^4 nodes it is impossible.
From brute force to the idea
- Find the waste. Heap positions reserve space for every missing descendant of a missing node, which explodes for deep trees.
- Mark only the empty spots you meet. Walk the tree in preorder. Write each value, and write one
#for each empty child. Below a#nothing is written, so the output has n values and n + 1 markers. - Read it back the same way.
deserializetakes tokens from one shared iterator.make()reads a token:#means an empty spot; otherwise it creates the node, then builds the left subtree, then the right, exactly the order they were written. - Separate tokens. Commas keep multi-digit and negative values like
-1and10apart, andint(t)turns them back into numbers.
This is the key idea: preorder with an explicit marker for every empty child records the shape exactly, and a recursive reader consumes the tokens in the same order.
A level-order version with # markers (LeetCode's own format) also works; both are O(n).
The key idea
Preorder with null markers makes the encoding unambiguous; decoding reads the tokens back in the same order. O(n).
Python solution
def serialize(root):
out = []
def walk(n):
if not n:
out.append("#"); return # mark empty spots
out.append(str(n.val)); walk(n.left); walk(n.right)
walk(root)
return ",".join(out)
def deserialize(data):
tokens = iter(data.split(","))
def make():
t = next(tokens)
if t == "#": return None
n = Node(int(t)); n.left = make(); n.right = make()
return n
return make()In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.
Complexity
| Approach | Time | Space |
|---|---|---|
| Brute force (heap positions) | O(2^h) in the worst case: one slot per position up to the deepest node | O(2^h): the string itself |
| Preorder with markers (shown code) | O(n): each node and each empty child written and read once | O(n): the string has 2n + 1 tokens, plus O(h) recursion |
Edge cases
- Empty tree: serialises to
"#", which deserialises toNone. - Single node:
"1,#,#". - Negative values:
[-1, 10]becomes"-1,10,#,#,#"and comes back unchanged. - Example tree
[1, 2, 3, null, null, 4, 5]:"1,2,#,#,3,4,#,#,5,#,#". - Very deep tree:
serializerecurses once per level, so a chain of about 1,000 nodes exceeds Python's default recursion limit, and LeetCode allows 10^4 nodes.deserializealso recurses per level. An explicit stack or a level-order (BFS) version avoids this. - The page leaves out the
Nodeclass (the usualval,left,right).
Common mistakes
- Leaving out the empty markers, so
[1, 2]and[1, null, 2]produce the same text. - Joining values without separators:
1then23and12then3both give "123". - Rebuilding with a fresh index in each call instead of one shared position, so the same token is read twice.
- Building the right child before the left while reading in preorder.
If the tree is a binary search tree (BST: smaller left, bigger right, unique values), the empty markers can be dropped (LeetCode 449). Write serialize and deserialize that store only the values. Describe your approach, then write it if you like.
Compare with our answer
Write the plain preorder. When reading back, the BST order says where a value belongs: carry bounds (lo, hi) down, and a value outside the bounds cannot be in this subtree, so this spot is empty.
from math import inf
def ser_bst(root):
out = []
def walk(n):
if n:
out.append(str(n.val))
walk(n.left)
walk(n.right)
walk(root)
return ",".join(out)
def des_bst(data):
vals = [int(t) for t in data.split(",")] if data else []
i = 0
def make(lo, hi):
nonlocal i
if i == len(vals) or not (lo < vals[i] < hi):
return None
node = Node(vals[i])
i += 1
node.left = make(lo, node.val)
node.right = make(node.val, hi)
return node
return make(-inf, inf)
Both are O(n) time. The empty tree serialises to "".
A strong answer mentions: why the BST order replaces the markers, passing bounds down while reading, and one shared position in the token list.
1. You must save a file-system tree (folders with any number of children) to text and restore it exactly. Which approach fits best?
Recording the child count does the job of the empty markers: the reader knows how many subtrees to build next. Plain preorder loses the shape, and heap positions grow exponentially with depth. Sorted full paths lose the original order of each folder's children.
2. Why is the shown format O(n) in size, unlike heap positions?
A tree with n nodes has exactly n + 1 empty child spots, so the text has 2n + 1 tokens whatever the shape. Heap positions also reserve space below missing nodes.
3. A learner drops the # markers and writes plain preorder values. Which pair of different trees now gives the same text?
Both trees in the first pair write 1,2: the 2 might be a left or a right child, and without markers the reader cannot tell. The other pairs list their values in different orders, so even unmarked preorder separates them.
Score 60% or more and the lesson is marked complete.