Serialisation

A tree in memory is a web of objects joined by references. To save it to a file or send it to another computer, it must become a flat piece of text, and then be rebuilt exactly. Turning a structure into text is called serialisation; turning the text back is called deserialisation.

Why write a tree as text

A reference only means something inside the running program. Write a node to a file and its left and right are meaningless addresses. So the text must describe the shape in some other way. Many everyday formats are serialised trees: a JSON file, an HTML page, the folders in a zip file.

Lesson 3 showed that one traversal list does not fix a tree, but two do. Two lists would mean writing every value twice, and the values would have to be different. A better idea fixes the tree with one list.

Pre-order with markers

Write the tree in pre-order, and also write a marker, such as #, wherever a child is missing. The markers say exactly where each subtree ends, so the reader never has to guess. Step through the first variant:

def serialize(root):
    out = []
    def write(node):
        if node is None:
            out.append('#')
            return
        out.append(str(node.value))
        write(node.left)
        write(node.right)
    write(root)
    return ' '.join(out)          # '1 2 # # 3 4 # # 5 # #'

A tree with n nodes has exactly n + 1 missing children. (Each of the n nodes has 2 child places, 2n in all, and n − 1 of them are filled by the edges; 2n − (n − 1) = n + 1.) So the text has 2n + 1 tokens. The parts are collected in a list and joined once at the end; adding to a string with += in a loop can copy the string again and again.

Reading it back

Read the tokens in the same order they were written, with the same rule. A marker means “no node here”. A value means “make a node, then read its left subtree, then its right subtree”. Step through the second variant.

def deserialize(data):
    tokens = iter(data.split())
    def read():
        t = next(tokens)
        if t == '#':
            return None
        node = TreeNode(int(t))
        node.left = read()
        node.right = read()
        return node
    return read()

iter(...) makes an iterator, and each next(tokens) takes the next token. All the calls share the one iterator, so each token is used exactly once, in order. This is the same shared position as nxt in lesson 3.

Why is the result right? By induction on the size of the tree: read() consumes exactly the tokens that write produced for one subtree, and returns that subtree. For a marker, that is one token. For a node, it is the value, then (by induction) exactly the left subtree’s tokens, then exactly the right subtree’s. Both functions are O(n).

Other formats

• Level order with markers, the format the practice problems use: [1, 2, 3, None, None, 4, 5]. It is easy to read by eye. Trailing markers can be dropped, because the reader can tell that the list has run out.
• Nested brackets: 1(2)(3(4)(5)), or nested lists [1, [2], [3, [4], [5]]]. These read like the tree’s shape. JSON is this idea with names for the parts.
• An array for a complete tree: if every level is full except the last (filled from the left), no markers are needed at all. Store the values level by level; the children of position i are at 2i + 1 and 2i + 2. Heaps are stored exactly like this (HEAP station).

Python’s pickle module can save almost any object, trees included, but it is Python-only and must never be used on data from strangers: loading a pickle can run code. json is safe and works across languages, but it handles only dicts, lists, strings, numbers and booleans, so a tree must first be turned into nested lists or dicts.