DSA Serializing a Binary Tree

The problem

Serializing a binary tree writes the whole tree as one string. Deserializing reads that string and rebuilds the tree exactly. Exactly means the same values in the same positions, with the same shape.

The format in this article writes values in preorder, joined by commas. A missing child is written as the marker #. The test trees below are rebuilt from their strings alone, and the round trip is the walkthrough's job.

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

def serialize(node, tokens):
    if node is None:
        tokens.append("#")
        return
    tokens.append(str(node.value))
    serialize(node.left, tokens)
    serialize(node.right, tokens)

def to_string(root):
    tokens = []
    serialize(root, tokens)
    return ",".join(tokens)

tree = TreeNode(5,
                TreeNode(3, TreeNode(1), TreeNode(4)),
                TreeNode(8, TreeNode(7), TreeNode(9)))

small = TreeNode(5, TreeNode(3), TreeNode(8))
for name, root in [("main tree", tree), ("small tree", small),
                   ("single node", TreeNode(7)), ("empty tree", None)]:
    print(name, "- serial:", to_string(root))

Read the main string slowly. Its value tokens are the preorder walk of the tree. Its # tokens sit exactly where children are missing, and they carry the shape.

Intuition: preorder alone loses the shape

A first idea writes only the preorder values. The string is short and easy to produce. It also throws away every fact about where the missing children are.

Two different trees can share one preorder list. The run below builds two such trees. Their preorder lists match, and their inorder lists prove the trees are different.

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

def preorder_values(node, order):
    if node is None:
        return
    order.append(node.value)
    preorder_values(node.left, order)
    preorder_values(node.right, order)

def inorder_values(node, order):
    if node is None:
        return
    inorder_values(node.left, order)
    order.append(node.value)
    inorder_values(node.right, order)

tree_a = TreeNode(5, TreeNode(3), TreeNode(8))
tree_b = TreeNode(5, None, TreeNode(3, None, TreeNode(8)))
for name, root in [("tree A, root with two children", tree_a),
                   ("tree B, a right chain", tree_b)]:
    pre, ino = [], []
    preorder_values(root, pre)
    inorder_values(root, ino)
    print(name, "- preorder:", pre, " inorder:", ino)

A reader given only 5,3,8 cannot choose between these trees. The format needs extra information. Every fix in this article is a way of putting the shape back into the string.

Brute force: write two traversals instead

One working fix writes two lists, the preorder list and the inorder list, joined as one string. The reader rebuilds the tree from the pair. That rebuild is the split method from the building-a-tree article.

The fix works on unique values. Its weaknesses are real. It writes every value twice, and it fails when values repeat, because the inorder split needs one position per value.

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

def walks(node, pre, ino):
    if node is None:
        return
    pre.append(str(node.value))
    walks(node.left, pre, ino)
    ino.append(str(node.value))
    walks(node.right, pre, ino)

def build(preorder, index_map, pre_index, low, high):
    if low > high:
        return None
    value = preorder[pre_index[0]]
    pre_index[0] += 1
    node = TreeNode(value)
    split = index_map[value]
    node.left = build(preorder, index_map, pre_index, low, split - 1)
    node.right = build(preorder, index_map, pre_index, split + 1, high)
    return node

def round_trip_two_lists(root):
    pre, ino = [], []
    walks(root, pre, ino)
    values = [int(item) for item in pre]
    inorder = [int(item) for item in ino]
    index_map = {value: index for index, value in enumerate(inorder)}
    rebuilt = build(values, index_map, [0], 0, len(inorder) - 1)
    pre2, ino2 = [], []
    walks(rebuilt, pre2, ino2)
    return ",".join(pre) + "|" + ",".join(ino), pre2 == pre and ino2 == ino, len(pre) + len(ino)

tree = TreeNode(5,
                TreeNode(3, TreeNode(1), TreeNode(4)),
                TreeNode(8, TreeNode(7), TreeNode(9)))

serial, matched, tokens = round_trip_two_lists(tree)
print("two-list serial:", serial)
print("round trip matches:", matched)
print("tokens written:", tokens)

The round trip matches on the main tree. The token count is 14 for seven nodes, two per node. The marker format below writes a comparable count and removes the uniqueness condition.

The optimal solution: one preorder stream with null markers

One preorder stream that writes # for every missing child carries both the values and the shape in a single pass. That one sentence is the whole method.

The reader consumes tokens in the same order the writer wrote them. A value token creates a node and then reads its left subtree and its right subtree. A # token returns an empty child at once, so the stream is never ambiguous.

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

def serialize(node, tokens):
    if node is None:
        tokens.append("#")
        return
    tokens.append(str(node.value))
    serialize(node.left, tokens)
    serialize(node.right, tokens)

def to_string(root):
    tokens = []
    serialize(root, tokens)
    return ",".join(tokens)

def deserialize(tokens):
    token = next(tokens)
    if token == "#":
        return None
    node = TreeNode(int(token))
    node.left = deserialize(tokens)
    node.right = deserialize(tokens)
    return node

tree = TreeNode(5,
                TreeNode(3, TreeNode(1), TreeNode(4)),
                TreeNode(8, TreeNode(7), TreeNode(9)))

small = TreeNode(5, TreeNode(3), TreeNode(8))
for name, root in [("main tree", tree), ("small tree", small),
                   ("single node", TreeNode(7)), ("empty tree", None)]:
    serial = to_string(root)
    rebuilt = deserialize(iter(serial.split(",")))
    print(name, "- serial:", serial, " round trip matches:", to_string(rebuilt) == serial)

Every test tree round-trips exactly. The check compares full serial strings, not just traversals. Equal serial strings mean equal values and equal shape, position by position.

Walkthrough: reading one string back, token by token

The walkthrough writes the small tree first. It then reads the string back with a traced reader. Each line shows one token being consumed and what that token builds.

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

def deserialize_traced(tokens, depth):
    token = next(tokens)
    if token == "#":
        print("  " * depth + "token # - empty child, return None")
        return None
    print("  " * depth + "token", token, "- make node", token)
    node = TreeNode(int(token))
    node.left = deserialize_traced(tokens, depth + 1)
    node.right = deserialize_traced(tokens, depth + 1)
    return node

def inorder_values(node, order):
    if node is None:
        return
    inorder_values(node.left, order)
    order.append(node.value)
    inorder_values(node.right, order)

small = TreeNode(5, TreeNode(3, TreeNode(1), TreeNode(4)), TreeNode(8))
tokens = []
def serialize(node, out):
    if node is None:
        out.append("#")
        return
    out.append(str(node.value))
    serialize(node.left, out)
    serialize(node.right, out)
serialize(small, tokens)
print("serial:", ",".join(tokens))
rebuilt = deserialize_traced(iter(tokens), 0)
order = []
inorder_values(rebuilt, order)
print("rebuilt inorder:", order)

The first token makes the root. Each # closes one empty child slot and lets the reader move on. No token is ever reread, and no position is guessed.

The rebuilt inorder list is read off at the end. It matches the small tree's inorder walk. Combined with the matching serial check in the previous section, the shape is proven kept.

Complexity

Writing and reading each touch every token once, so both take O(n) time for a tree of n nodes. The two-list format has the same time, because it also touches each of its tokens once.

The serial string itself holds O(n) tokens under either format. A tree of n nodes writes n value tokens and n plus one null markers in the marker format, for a total of 2n plus one tokens.

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

def serialize(node, tokens):
    if node is None:
        tokens.append("#")
        return
    tokens.append(str(node.value))
    serialize(node.left, tokens)
    serialize(node.right, tokens)

def to_string(root):
    tokens = []
    serialize(root, tokens)
    return ",".join(tokens)

def complete_tree(values):
    if not values:
        return None
    mid = len(values) // 2
    return TreeNode(values[mid], complete_tree(values[:mid]),
                    complete_tree(values[mid + 1:]))

for n in [3, 7, 15]:
    root = complete_tree(list(range(1, n + 1)))
    tokens = []
    serialize(root, tokens)
    markers = sum(1 for token in tokens if token == "#")
    print("nodes", n, "- two-list tokens:", 2 * n,
          " marker tokens:", len(tokens), " of which null markers:", markers)

The counts prove the token claim. Marker tokens grow by exactly the formula at each size. The gain over two lists is not size but strength, since one stream now handles repeated values.

Edge cases and pitfalls

An empty tree serializes to a single #. A single node writes its value and two markers. Both round-trip through the same code as the large trees, with no special cases.

Repeated values are safe in the marker format. The run below round-trips a tree of three copies of 5. The two-list format from the brute force section cannot rebuild that tree at all.

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

def serialize(node, tokens):
    if node is None:
        tokens.append("#")
        return
    tokens.append(str(node.value))
    serialize(node.left, tokens)
    serialize(node.right, tokens)

def to_string(root):
    tokens = []
    serialize(root, tokens)
    return ",".join(tokens)

def deserialize(tokens):
    token = next(tokens)
    if token == "#":
        return None
    node = TreeNode(int(token))
    node.left = deserialize(tokens)
    node.right = deserialize(tokens)
    return node

print("empty tree serial:", to_string(None))
print("empty tree rebuilt:", deserialize(iter(["#"])))
dup = TreeNode(5, TreeNode(5), TreeNode(5))
serial = to_string(dup)
rebuilt = deserialize(iter(serial.split(",")))
print("duplicate values serial:", serial)
print("duplicate round trip matches:", to_string(rebuilt) == serial)
try:
    deserialize(iter(["5", "3"]))
    print("truncated input: no error")
except StopIteration:
    print("truncated input fails with: StopIteration")

A truncated string is the remaining pitfall. The reader trusts the stream to be complete and fails loudly when it ends early. Producers must write the markers, all of them, every time.