Serialize and Deserialize a Binary Tree With Preorder and Null Markers

A tree in memory is a web of pointers, and pointers do not survive a file, a cache or a network socket. To send one you have to flatten it into a string, and to use it again you have to rebuild exactly the same shape from that string. The whole problem hides in one detail: the values alone are not enough, and the fix is to write down the gaps.

The problem it solves

Write serialize(root), which turns a binary tree into a string, and deserialize(text), which turns that string back into a tree with the same values in the same positions. The format is yours to design; the only requirement is the round trip, deserialize(serialize(t)) equal to t.

The obvious first attempt is to write the values in some traversal order. It fails immediately:

• Preorder of "1 with a left child 2" is 1, 2.
• Preorder of "1 with a right child 2" is also 1, 2.

Two different trees, one string. No reader can tell which one was meant.

The intuition

What was lost is where the children are not. So write a marker, here #, every time the walk reaches an empty child. Now the two trees above become 1,2,#,#,# and 1,#,2,#,#, and they are different strings.

Why is preorder with markers enough to rebuild? Because preorder writes a node before either subtree, and the markers say exactly where each subtree ends. Reading the tokens left to right, the rebuild does the same walk:

• Take the next token. If it is #, this position is empty.
• Otherwise it is a node's value. Build its left subtree from the tokens that follow, and when that call returns, the stream is sitting exactly at the start of the right subtree.

No lookahead, no second pass, no counting. Each recursive call consumes precisely the tokens its subtree produced.

Watch it run

The animation serialises the tree with root 1, a left child 2, and a right child 3 that has a left child 4. The strip at the bottom is the wire: it fills left to right on the way out, # cells marking each gap, and ends as the 9 tokens 1,2,#,#,3,4,#,#,#. Then the same strip is consumed left to right, and the tree reappears node by node in the order the tokens are read.

The code

Preorder with null markers. The rebuild uses an iterator instead of tokens.pop(0); popping from the front of a Python list shifts every remaining element, which would make the rebuild quadratic:

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

def serialize(root):
    out = []
    def walk(node):
        if node is None:
            out.append("#")                    # the gap is written down
            return
        out.append(str(node.val))
        walk(node.left)
        walk(node.right)
    walk(root)
    return ",".join(out)

def deserialize(text):
    tokens = iter(text.split(","))
    def build():
        t = next(tokens)                       # read strictly forwards
        if t == "#":
            return None
        node = Node(int(t))
        node.left = build()                    # left subtree first,
        node.right = build()                   # exactly as it was written
        return node
    return build()

root = Node(1, Node(2), Node(3, Node(4)))
text = serialize(root)
print(text)                                    # 1,2,#,#,3,4,#,#,#
print(serialize(deserialize(text)) == text)    # True
print(serialize(None))                         # #

The ambiguity from the start of the article, reproduced, and fixed by the markers:

def preorder_values(node):
    if node is None:
        return []
    return [node.val] + preorder_values(node.left) + preorder_values(node.right)

a = Node(1, Node(2))                           # 2 is a left child
b = Node(1, None, Node(2))                     # 2 is a right child
print(preorder_values(a), preorder_values(b))  # [1, 2] [1, 2]
print(serialize(a), serialize(b))              # 1,2,#,#,# 1,#,2,#,#

A level-order format also works, and it reads naturally when you print a tree row by row. It writes children in breadth-first order, again with a marker for each missing child, and the rebuild attaches children to parents in the same queue order:

from collections import deque

def serialize_bfs(root):
    out, queue = [], deque([root])
    while queue:
        node = queue.popleft()
        if node is None:
            out.append("#")
            continue
        out.append(str(node.val))
        queue.append(node.left)
        queue.append(node.right)
    return ",".join(out)

def deserialize_bfs(text):
    tokens = text.split(",")
    if tokens[0] == "#":
        return None
    root = Node(int(tokens[0]))
    queue, i = deque([root]), 1
    while queue:
        node = queue.popleft()
        for side in ("left", "right"):
            if tokens[i] != "#":
                child = Node(int(tokens[i]))
                setattr(node, side, child)
                queue.append(child)
            i += 1
    return root

print(serialize_bfs(root))                     # 1,2,3,#,#,4,#,#,#

Both formats round-tripped on 2,000 random trees with repeated and negative values, compared node by node, plus a check of the token count:

import random

def random_tree(n):
    if n == 0:
        return None
    left = random.randint(0, n - 1)
    return Node(random.randint(-50, 50), random_tree(left), random_tree(n - 1 - left))

def same(x, y):
    if x is None or y is None:
        return x is y
    return x.val == y.val and same(x.left, y.left) and same(x.right, y.right)

random.seed(12)
ok = True
for _ in range(2000):
    t = random_tree(random.randint(0, 15))
    ok &= same(deserialize(serialize(t)), t)
    ok &= same(deserialize_bfs(serialize_bfs(t)), t)
    ok &= len(serialize(t).split(",")) == 2 * len(preorder_values(t)) + 1
print(ok)                                      # True

The complexity

A binary tree with n nodes has exactly n + 1 empty child positions, so the preorder string always has 2n + 1 tokens, which is what the last check confirms. Both functions touch each token once: O(n) time and O(n) space for the string.

The recursion adds O(h) stack space, where h is the tree's height. For a balanced tree that is O(log n); for a tree that is really a linked list, it is O(n). The level-order version uses a queue instead of recursion, O(w) for the widest level, and never recurses.

Where it goes wrong

• Leaving out the markers. Values alone in one traversal order do not identify a tree, as the two-node example shows. Preorder plus inorder together can, but only if values are unique.
• pop(0) on a list. Correct, but each pop is O(n), so the rebuild becomes O(n²). Use an iterator, a deque, or an index.
• Deep trees and the recursion limit. CPython's default recursion limit is about 1,000 frames, so a very skewed tree can raise RecursionError. The BFS format, or an explicit stack, avoids it.
• A separator that can appear in the data. Commas work for integers. For string values, escape the separator or length-prefix each token, the same problem as encoding a list of strings.

How to say it in an interview

"Values alone are ambiguous, so I write a marker for every null child. I serialise in preorder: the node, then its left subtree, then its right. To rebuild, I read tokens in order: a marker means null; otherwise I create the node and recursively build left, then right, and each call consumes exactly its own subtree's tokens. A tree with n nodes gives 2n plus 1 tokens, so both directions are O(n) time and space, plus O(h) recursion. If the tree can be very deep, I'd switch to the level-order format with a queue."

Preorder itself is one of the walks in tree traversals, the level-order format is level order traversal with gaps written down, and escaping string values is the subject of encode and decode strings.