Tree Serialization and Deserialization: Preorder and Level Order

To serialize a binary tree, walk it in a fixed order and write a marker such as null for every missing child. To deserialize, read the tokens back in the same order. The markers are what make the result unambiguous: without them, a list of values cannot tell you where the branches are. This is the problem behind LeetCode 297, “Serialize and Deserialize Binary Tree”, and the two standard answers are preorder (depth-first) and level order (breadth-first). Both are below, with code that has been run.

The setup

All the code uses this node class. The functions must work for any tree, including an empty tree, a single node, a skewed tree and negative values.

from collections import deque

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

The example tree used throughout:

#      1
#     / \
#    2   3
#       / \
#      4   5
root = TreeNode(1, TreeNode(2), TreeNode(3, TreeNode(4), TreeNode(5)))

Why you need null markers

The preorder values of this tree are 1,2,3,4,5. So are the preorder values of a right-leaning chain 1 -> 2 -> 3 -> 4 -> 5. One traversal of values alone does not identify a tree. (For a binary search tree it does, because the ordering rule tells you where each value goes. That special case is covered near the end.) For a general binary tree, record the empty children too, and the traversal becomes reversible.

Approach 1: preorder with null markers

Visit the node, then the left subtree, then the right subtree. Emit null whenever you hit an empty child.

def serialize_preorder(root):
    out = []
    def dfs(node):
        if node is None:
            out.append("null")
            return
        out.append(str(node.val))
        dfs(node.left)
        dfs(node.right)
    dfs(root)
    return ",".join(out)

def deserialize_preorder(data):
    tokens = iter(data.split(","))
    def build():
        tok = next(tokens)
        if tok == "null":
            return None
        node = TreeNode(int(tok))
        node.left = build()
        node.right = build()
        return node
    return build()

For the example tree this prints:

1,2,null,null,3,4,null,null,5,null,null

How deserialization reads it back

The shared iterator is the whole trick. Each call to build() consumes exactly the tokens of one subtree, then returns, so the next call starts at the right place.

1. 1: create node 1, then build its left subtree.
2. 2: create node 2, build its left subtree. The next token is null, so left is empty. The token after is null too, so right is empty. Node 2 is a leaf; return it.
3. Back at node 1, build the right subtree. 3 becomes a node; its left reads 4, null, null (a leaf), its right reads 5, null, null.
4. All tokens are used and the tree is rebuilt.

Serializing the rebuilt tree gives the same string back, which confirms the round trip.

Approach 2: level order (BFS) with null markers

This is the format LeetCode uses to display trees, so it is the one you see in examples like [1,2,3,null,null,4,5]. Use a queue, and push both children of every real node, including missing ones.

def serialize_level(root):
    if root is None:
        return ""
    out, queue = [], deque([root])
    while queue:
        node = queue.popleft()
        if node is None:
            out.append("null")
        else:
            out.append(str(node.val))
            queue.append(node.left)
            queue.append(node.right)
    while out[-1] == "null":   # trailing nulls carry no information
        out.pop()
    return ",".join(out)

def deserialize_level(data):
    if not data:
        return None
    tokens = data.split(",")
    root = TreeNode(int(tokens[0]))
    queue, i = deque([root]), 1
    while queue and i < len(tokens):
        node = queue.popleft()
        if i < len(tokens) and tokens[i] != "null":
            node.left = TreeNode(int(tokens[i]))
            queue.append(node.left)
        i += 1
        if i < len(tokens) and tokens[i] != "null":
            node.right = TreeNode(int(tokens[i]))
            queue.append(node.right)
        i += 1
    return root

For the example tree this prints:

1,2,3,null,null,4,5

How deserialization reads it back

Tokens are consumed two at a time, as the left and right child of the next node in the queue. Only real nodes enter the queue, so each node in it is waiting for its children.

1. Root is 1. Queue: [1]. Read 2, 3: they become the children of 1. Queue: [2, 3].
2. Pop 2. Read null, null: no children. Queue: [3].
3. Pop 3. Read 4, 5: its children. Queue: [4, 5].
4. Pop 4 and 5: tokens are used up, the loop ends.

Note that the output omits the nulls under 4 and 5. Trailing nulls are redundant because the reader stops when the tokens run out. Without trimming, the string would be 1,2,3,null,null,4,5,null,null,null,null.

Which one to use

	Preorder	Level order
Time	O(n)	O(n)
Extra space	O(h) call stack, plus the output	O(w) queue, where w is the widest level, plus the output
Code	Shortest; recursion mirrors the tree	Iterative; no recursion limit
Output size	n values and n + 1 nulls	Same, minus the trailing nulls
Matches LeetCode’s display format	No	Yes

Here n is the number of nodes and h is the height. In the worst case h = n (a skewed tree). In an interview, preorder is usually the faster one to write correctly. Choose level order when the format matters or the tree can be very deep. Both visit every node once, so time is linear either way.

Edge cases to test

These cases were all run against both pairs of functions:

• Empty tree. Preorder gives null, which reads back as None. The level-order version above returns an empty string, which also reads back as None.
• Single node. TreeNode(-7) gives -7,null,null in preorder. Negative values work because the separator is a comma and values are parsed with int().
• Left-skewed tree (1 with left child 2 with left child 3). Preorder: 1,2,3,null,null,null,null. Level order: 1,2,null,3.
• Duplicate values. No problem, because structure comes from the null markers, not the values.
• Deep trees. A left chain of 5,000 nodes made the recursive preorder serializer raise RecursionError in CPython, whose default recursion limit is 1,000. The level-order version handled it. If the input can be that deep, use an iterative traversal with an explicit stack or the BFS format.

Common mistakes

• Omitting the nulls. Values alone are ambiguous, as shown above.
• Ambiguous separators. If you join values with no delimiter, 1,23 and 12,3 become the same string. Use a delimiter and parse tokens, not characters.
• Using an empty-string token for null and then splitting on commas. It works, but "1,,," is easy to get wrong when trimming. An explicit null token (or #) is clearer.
• Forgetting that deserialization must consume tokens in the same order as serialization wrote them. Mixing a preorder writer with a level-order reader gives wrong trees without any error.
• Appending to a string in a loop in languages where that copies. Collect tokens in a list and join once.

Follow-up questions an interviewer asks

Serialize a binary search tree compactly

This is LeetCode 449. Because of the BST ordering rule, the preorder values alone are enough: no null markers. To rebuild, insert values in order, or use the bounds trick: recursively take the next value if it lies between (low, high). That gives O(n) time and a shorter string.

Serialize an N-ary tree

There are no left and right slots, so write each node’s value followed by its child count, in preorder. The tree with root 1, children 3, 2, 4, and node 3 having children 5, 6, becomes 1 3 3 2 5 0 6 0 2 0 4 0. Reading it back: take a value, take a count k, then build k children recursively. The round trip matched when run.

class Node:
    def __init__(self, val, children=None):
        self.val = val
        self.children = children or []

def serialize_nary(n):
    return f"{n.val} {len(n.children)}" + "".join(" " + serialize_nary(c) for c in n.children)

def deserialize_nary(s):
    tokens = iter(s.split())
    def build():
        val, k = int(next(tokens)), int(next(tokens))
        return Node(val, [build() for _ in range(k)])
    return build()

What if node values are strings that may contain commas?

Then the delimiter is no longer safe. Either escape the delimiter, prefix each value with its length (3:abc), or use a real format such as JSON.

What about a tree with cycles, or a general graph?

Preorder would loop forever. Give each node an id, keep a map of nodes already written, and emit a reference to the id instead of re-visiting. This is how most real serializers handle shared or cyclic object graphs.

Can you do it in less space?

The output must hold n values, so O(n) is the floor for the string. You can shrink the nulls with a bitmap for structure plus a separate list of values, or compress the text, but the interview answer is usually just to explain the O(n) bound and the trade-off.

Where this is used outside interviews

The same idea, flattening a hierarchy to a sequence that can be rebuilt, appears when you save a document tree or a scene graph, send a nested structure over the network, or store a decision tree from a machine learning library. In practice you rarely hand-roll the format: you use JSON, Protocol Buffers or the library’s own save function, and your job is choosing which fields to keep. The interview version is practice for reasoning about traversal order and reversibility.

Practice

If tree traversals still feel shaky, rehearse them first, since serialization is just a traversal with markers. The Level Order Traversal and Post Order Tree Traversal lessons cover the two orders used here, and this overview of trees covers the basics. Then solve LeetCode 297 yourself without looking, using both formats, and test the edge cases above. For more guided problems with step-by-step help, see AlgoCademy.