Serialization flattens a binary tree into a storable string, usually by walking it in pre-order or level-order and writing a marker such as # for every empty child. Deserialization is the exact inverse: it reads that string back and rebuilds the identical tree. In short, serialize turns a tree into text for storage or transfer, and deserialize turns the text back into a tree.
Serializing and deserializing a binary tree is a classic data-structures problem, and it is LeetCode 297 in interviews. Managing tree structures efficiently requires understanding both operations. One converts a tree into a portable format, while the other reconstructs it from that format.
The core idea is that the two are inverses. Serialization bridges an in-memory structure and its persistent form, whereas deserialization breathes life back into the hierarchy. This guide defines each operation, shows the code and the null-marker trick, compares them in detail, and explains when each matters.
If you are still mapping out tree basics, it helps to know the difference between a binary tree and a binary search tree first.
What is Serialization?
Binary tree serialization transforms a tree into a compact, portable format, usually a string. That flat form is easy to store in a file, save in a database, or send over a network. So serialization is the bridge between an in-memory data structure and its persistent or transferable counterpart.
The method is a traversal. You walk the tree in a fixed order, writing each node’s value as you go, and you write a marker such as # or null whenever a child is missing. Those markers are essential, because they record the tree’s shape, not just its values.
Advantages of serialization:
- Produces a compact string that is easy to store or transmit.
- Straightforward to implement, since it is a linear traversal.
- Preserves the exact structure when null markers are included.
- Language-neutral, so any system can read the format.
Disadvantages of serialization:
- Null markers add extra characters, so the string grows.
- The format must be agreed in advance by both sides.
What is Deserialization?
Binary tree deserialization is the reverse: it reconstructs the tree from its serialized form. This is the operation you run when retrieving stored data or receiving it over a network, and it restores the full hierarchical structure.
Deserialization usually uses recursion. The algorithm descends through the serialized string, consuming one token at a time and building nodes as it goes. When it meets a null marker, it returns nothing, which correctly leaves that child empty. The process continues until the whole string is consumed.
Advantages of deserialization:
- Restores the exact original tree, node for node.
- Recursion keeps the algorithm short and readable.
- Runs in linear time when the format includes null markers.
Disadvantages of deserialization:
- Recursive descent uses stack space, which deep trees can strain.
- It fails if the format or the markers do not match the writer.
Serialize vs Deserialize: Comparison Table
| Aspect | Serialize | Deserialize |
|---|---|---|
| Purpose | Convert a tree into a storable format | Rebuild the tree from that format |
| Input | Binary tree (in memory) | String or byte stream |
| Output | String or byte stream | Binary tree (in memory) |
| Direction | Flatten (tree to text) | Rebuild (text to tree) |
| Core technique | Traversal (pre-order or level-order) | Recursion or a queue, in the same order |
| Null handling | Writes a marker such as # for empty children | Reads the marker and leaves that child empty |
| Time complexity | O(n), visits each node once | O(n), consumes each token once |
| Space complexity | O(n) for the output string | O(n) for the tree, plus O(h) call stack |
| Typical use | Saving, caching, or sending a tree | Loading or receiving a tree |
| Order of operations | Runs first, before storage or transfer | Runs second, after retrieval |
| Main risk | Losing shape if markers are omitted | Corrupt output if the format mismatches |
| Relationship | Exact inverses: deserialize(serialize(tree)) returns the same tree | |
Traversal Orders and Null Markers
The traversal order decides the format, so both sides must use the same one.
Pre-order visits the root first, then the left subtree, then the right. It is the most common choice, because the root arrives first, so a recursive rebuild can create each node before its children. Post-order visits the left and right subtrees before the root, and it also rebuilds uniquely, though you read the string in reverse and build the right child before the left. Level-order, or breadth-first, writes the tree row by row using a queue, which is the format LeetCode shows.
In-order is the exception. An in-order sequence alone cannot rebuild a binary tree, because many different trees produce the same in-order output. So in-order only works when it is paired with a pre-order or post-order sequence, which is a separate classic problem.
Null markers matter just as much. Without them, a root with only a left child and a root with only a right child would serialise to the same node list. The markers record which side is empty, so the shape survives the round trip.
Python Code
Here is the standard pre-order solution, with # as the null marker. Serialization walks the tree, and deserialization consumes the same tokens in the same order.
class Node:
def __init__(self, val, left=None, right=None):
self.val = val
self.left = left
self.right = right
def serialize(root):
"""Flatten a binary tree into a pre-order string."""
out = []
def walk(node):
if node is None:
out.append('#') # null marker keeps the shape
return
out.append(str(node.val))
walk(node.left)
walk(node.right)
walk(root)
return ','.join(out)
def deserialize(data):
"""Rebuild the binary tree from that string."""
tokens = iter(data.split(','))
def build():
token = next(tokens)
if token == '#':
return None
node = Node(int(token))
node.left = build()
node.right = build()
return node
return build()
# round trip: 1 -> (2, 3), 3 -> (4, 5)
tree = Node(1, Node(2), Node(3, Node(4), Node(5)))
text = serialize(tree)
print(text) # 1,2,#,#,3,4,#,#,5,#,#
print(serialize(deserialize(text)) == text) # True
Notice the symmetry. The writer appends a # for every missing child, and the reader returns None on every #. Because both sides follow the identical order, the round trip returns exactly the original tree, which the final check confirms.
When Each Matters
Serialization and deserialization always come as a pair, yet the workload decides which one you tune.
Serialization leads when data is written often: caching a tree, saving it to disk, or sending it across a network. Since it is a simple linear walk, the cost is predictable, so keeping the output compact matters most there.
Deserialization leads when data is read often, such as loading a saved structure at startup. Its recursion uses stack space, so very deep trees may need an iterative version instead. Therefore an application heavy on retrieval should watch the rebuild path more closely.
Interview Questions
Frequently Asked Questions
Wrapping Up
Serialization and deserialization are two halves of one round trip. Serialization walks a binary tree and flattens it into a string with null markers, while deserialization reads that string back and rebuilds the identical tree.
Remember the essentials: use pre-order or level-order, always write markers for empty children, and keep both sides on the same format. Both run in O(n), and in-order alone can never rebuild a tree. That is enough to answer most exam and interview questions on the pair.
Related reading on DiffStudy:
