Serialize and deserialize a binary tree in Python

Why this lesson matters

A program often needs to save a tree to a file, or send it over a network, or print it so a person can read it. A tree in memory is a set of linked objects, and those objects cannot be copied into a file as they are. The memory addresses change every time the program runs. So you need a text form: a string that says what the tree holds and how the nodes are joined. Turning the tree into text is called serialize. Turning the text back into a tree is called deserialize.

The main trap is that a list of values alone does not describe a tree. Two different trees can produce the same list. This lesson shows how a few extra marker words fix that, how to read the text back, and how to test the result so you know the round trip really works.

By the end of this lesson you will write serialize and deserialize in Python, rebuild a tree from its text, and check the round trip on a chain, a zigzag, a tree with negative numbers and a tree with one node. You will also see the errors you get when the text is wrong. The traversal idea used here, visiting the root before the children, is the preorder walk from the earlier lessons in this module. This lesson does not repeat that walk; it uses it as a tool.

The idea: values alone are not enough

Take two small trees. Tree A has the root 1 and one child 2 on its left. Tree B has the root 1 and one child 2 on its right. Both trees have two nodes and both hold the values 1 and 2. If you write down only the values in the order you visit them with a preorder walk, you get the same list for both:

tree A (2 on the left):  1, 2
tree B (2 on the right): 1, 2

Looking at 1, 2, you cannot tell which tree it came from. The list lost the shape. To keep the shape, you must also write down where a child is missing. The usual way is to write a marker word, here null, at each empty spot. Now the two trees look different:

tree A: 1,2,null,null,null
tree B: 1,null,2,null,null

Read tree A from left to right. The 1 is the root. The 2 is its left child. The first null says the left child of 2 is empty. The second null says the right child of 2 is empty. The third null says the right child of the root is empty. Five words describe exactly one tree.

The marker must be a word that cannot be a real value. In this lesson the values are whole numbers, and the word null is never a number, so there is no clash. If your values were text, you would pick a marker that the values never contain.

A worked example, step by step

Here is a bigger tree. Its root is 1. The root's left child is 2, and 2 has a left child 4. The root's right child is 3, and 3 has a left child 5 and a right child 6.

        1
       / \
      2   3
     /   / \
    4   5   6

To write it down, walk the tree in preorder: visit the node first, then the whole left subtree, then the whole right subtree. Each time you reach an empty spot, write null. Here is the walk, one line per step.

1. Visit 1. Write 1. Go left.
2. Visit 2. Write 2. Go left.
3. Visit 4. Write 4. Go left: it is empty, write null. Go right: it is empty, write null.
4. Back at 2, go right: it is empty, write null.
5. Back at 1, go right. Visit 3. Write 3. Go left.
6. Visit 5. Write 5. Go left and right: both empty, write null, null.
7. Back at 3, go right. Visit 6. Write 6. Go left and right: both empty, write null, null.

Join the words with commas and you get:

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

Six real values and seven null markers. The number of markers is always one more than the number of real nodes. Each node has two child spots, so a tree with n nodes has 2n spots. Every node except the root fills one spot, so n - 1 spots hold real nodes and n + 1 are empty. Here n is 6, so there are 7 markers.

Writing the text

Writing the text is a short recursive function. A recursive function is one that calls itself on a smaller piece of the problem. Here the smaller piece is a subtree. The function has a base case, the empty tree, which writes one null and stops. For a real node it writes the value, then calls itself on the left child, then on the right child.

The function adds each word to a list, and at the end it joins the list with commas. The method ",".join(parts) joins a list of strings with a comma between each pair. A list is faster than joining strings in the middle of the recursion, because building a new string each time copies all the old text again.

The class below takes its children as optional arguments. TreeNode(1, left, right) builds a node with its children already attached, and a child you leave out is None.

Output:

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

The output matches the hand walk above. The order of the words is the order of the walk, and the null markers are placed in the same spots.

Reading the text back

To rebuild the tree, you read the words in the same order they were written. The first word is the root. The next block of words describes the left subtree, and the block after that describes the right subtree. You do not need to know where one block ends and the next begins, because each call to the reader consumes exactly the words that its own subtree needs. That is the reason the markers are required: without them, the reader cannot tell when a left subtree stops.

The reader keeps a queue of words. A queue is a line where you take items from the front. In Python, collections.deque is the right tool, and popleft() takes the front word. Each call takes the front word. If the word is null, the call returns an empty spot. Otherwise it creates a node with that value and makes two more calls, one for the left child and one for the right child.

Here is the reading of the text 1,2,null,null,3,null,null, step by step:

1. Take 1. Make a root with value 1. Read the left child.
2. Take 2. Make a node with value 2. Read its left child.
3. Take null. The left child of 2 is empty. Read the right child of 2.
4. Take null. The right child of 2 is empty. Go back to the root and read its right child.
5. Take 3. Make a node with value 3. Read its left child.
6. Take null. Empty. Read the right child of 3.
7. Take null. Empty. The walk is done.

The queue is empty at the end, which is a good sign. A text that leaves words over is a bad input. The second example below shows a text that runs out early.

Output:

root 1, left 2, right 3
left of 2 is 4
right of 3 is 6
again: 1,2,4,null,null,null,3,5,null,null,6,null,null

The function read_preorder takes the words from the front of the same queue, so every call moves the queue forward and the next call sees the next word. The reader never needs an index number. The queue does that job.

Testing the round trip

A round trip means: start with a tree, serialize it, deserialize the text, and serialize again. If the two texts match, the rebuilt tree has the same values in the same shape. Here is why the check is sound. The text describes the tree exactly, so two trees with the same text have the same values and shape. A text that comes out the same after the trip is therefore the same description.

Test on many shapes, not only the one you wrote. The shapes below are the ones that most often break a first attempt.

Output:

empty tree: null
  same after round trip: True
one node: 7,null,null
  same after round trip: True
left chain 3-2-1: 3,2,1,null,null,null,null
  same after round trip: True
right chain 1-2-3: 1,null,2,null,3,null,null
  same after round trip: True
zigzag: 5,4,null,3,null,null,6,null,null
  same after round trip: True
negatives and zero: 0,-5,null,null,12,null,null
  same after round trip: True
full 1..7: 1,2,4,null,null,5,null,null,3,6,null,null,7,null,null
  same after round trip: True
duplicates: 2,2,null,null,2,null,null
  same after round trip: True

Each shape is worth a look.

The empty tree has no nodes, so the text is a single null. That is why the base case of the writer adds a marker instead of an empty string. If the writer wrote nothing for an empty tree, the text would be an empty string, and the reader would have no first word to take.

The one-node tree writes its value and two markers. A leaf is a node with two empty children, so it always produces two null words after it.

The two chains show that the text grows in a line and does not branch. A left chain writes null as the right child of every node. A right chain writes null as the left child of every node. Both chains use the same reader, and the reader does not care which way the chain leans.

The zigzag tree has a node with only a right child and a node with no children on the other side. Shapes like this are where a reader that assumes both children exist would fail.

The tree with -5 and 0 checks that the reader handles negative numbers and zero. int accepts a leading minus sign, and zero is a normal value, not an empty spot. The marker is the word null, so the number 0 does not confuse the reader.

The duplicate tree has the value 2 three times. The text does not need values to be distinct, because the markers carry the shape. Values can repeat without any problem.

More examples of increasing difficulty

Example 1: counting nodes from the text

Without building the tree, you can count its nodes from the text. Every word that is not null is one node, because each real node writes its own value once. The count of markers then follows from the count of nodes.

Output:

nodes: 6
nulls: 7
nulls minus nodes: 1

The sum(1 for ...) line counts the words that pass the test. Each word that passes adds 1, and the words that fail add nothing. It does the same job as a loop with a counter.

The difference is always 1. The text for a tree with n nodes always has n + 1 markers, so the difference is exactly one. This is a cheap check you can run on text from a file before you rebuild anything: if the difference is not 1, the text is damaged.

Example 2: an example with a missing marker

Now take a text that is one marker short. The tree has the root 1, a left child 2, and a right child 3. The correct text is 1,2,null,null,3,null,null. Suppose the last null was lost while copying the file, so the text is 1,2,null,null,3,null.

Output:

complete text, leftover words: 0, right of root: 3
damaged text: IndexError: pop from an empty deque

The reader ran out of words while it was still building the right child of 3. The error is an IndexError, which Python raises when popleft finds the queue empty. A good program checks the number of leftover words after a read. A text with extra words at the end is also damaged, even if it reads without an error.

Example 3: a tree that looks like a list

The last example is a tree whose values climb a long way down, like a linked list. The reader is recursive, so a very deep tree makes many nested calls. Each call uses stack memory, which is the small working area the program keeps for the calls that are still open. Python limits how many calls can be open at once, and the default limit is 1000. A chain of 1000 nodes needs more than 1000 open calls, because each node's missing child is a call of its own. This example shows that limit, and then a chain of 900 nodes that stays under it.

Output:

chain of 1000 nodes: RecursionError
chain of 900 nodes, words in text: 1801
text starts: 1,null,2,null,3,null

The chain of 900 nodes has 1,801 words: 900 values and 901 markers, which matches the rule from the first example. The text starts with 1,null,2 because the chain leans right, so every node's left child is empty.

The 1000-node chain fails on the default limit. You can read the limit with sys.getrecursionlimit(), and you can raise it with sys.setrecursionlimit(...). A higher limit lets this code run on a deeper tree, but it does not remove the problem. A chain of a million nodes would need a million open calls. For a very deep tree, write the reader and the writer with a list as an explicit stack, as the earlier lessons in this module did for the traversals.

Common mistakes

Leaving out the markers

If the text holds only the values, two different trees can give the same text, as shown in the first section. A reader cannot rebuild the right tree from such a text. The fix is always to write a marker at each empty spot. You can check this with a short test: build the two trees 1 with a left child 2, and 1 with a right child 2. Their values-only preorder lists are both [1, 2]. The text with markers is different for each tree.

Parsing an empty string

If the tree is empty and your writer returns an empty string for it, the reader receives "". The reader splits that string into one empty word, then tries to read it as a number. The code is shown without the run mark because it stops with an error.

int("")

The output is:

Traceback (most recent call last):
  File "main.py", line 1, in <module>
    int("")
    ~~~^^^^
ValueError: invalid literal for int() with base 10: ''

The fix is in the writer. An empty tree must write the marker null, not nothing.

Reading past the end of the text

When the text has too few words, the reader calls popleft on an empty queue. Python then raises an IndexError:

IndexError: pop from an empty deque

This is the same damaged text as in the second example. Check the word count and the leftover count after each read, and treat a mismatch as a bad input.

Reading the marker as a number

If you forget to check for the marker before converting the word to a number, int("null") fails with this message:

ValueError: invalid literal for int() with base 10: 'null'

The check if token == NULL_MARK must come before the call to int. Put the check first in the function, as the code in this lesson does.

Spaces next to the markers

int ignores spaces at the start and end of a number, so a word such as " 2" still reads as 2. The marker is different. The check token == "null" compares the whole word, so a space next to the marker makes the word not match, and then int fails on it. For example, the text 1, null,null gives the word " null":

int(" null")

ValueError: invalid literal for int() with base 10: ' null'

The writer uses ",".join(parts), which adds no spaces. If you write the text by hand or copy it from a document, remove the spaces, or call strip() on each word before comparing it with the marker.

Keeping the read position in a global variable

Some first attempts keep the read position in a global number, which goes up by one on each read. This works for one call. The second call starts at the old position, which is past the end of the words:

pos = 0
 
 
def read_word(words):
    global pos
    word = words[pos]
    pos += 1
    return word
 
 
first = "1,2,null,null,3,null,null".split(",")
for _ in range(7):
    read_word(first)
 
second = "5,null,null".split(",")
print(read_word(second))

The output is:

Traceback (most recent call last):
  File "main.py", line 16, in <module>
    print(read_word(second))
          ~~~~~~~~~^^^^^^^^
  File "main.py", line 6, in read_word
    word = words[pos]
           ~~~~~^^^^^
IndexError: list index out of range

Here the first text was read seven words long, so the position is 7, and the second text has only three words. The queue in this lesson avoids the problem, because a new queue is made for each call to deserialize. If you use a position number, reset it to 0 at the start of every call.

Practice

1. Write the preorder text, with markers, for this tree. The root is 8. Its left child is 3, and 3 has a left child 1. The root's right child is 10, and 10 has no left child and a right child 14. 14 has a left child 13.

Show the answer

The text is 8,3,1,null,null,null,10,null,14,13,null,null,null. Walk the tree in preorder and write null at each empty spot. The tree has 6 nodes, so the text has 7 markers. Counting the words of the text gives 13 in total, which is 6 values and 7 markers.

2. Explain why deserialize("") fails, and say what the writer should do for an empty tree instead.

Show the answer

Splitting "" on commas gives one empty word. The reader takes that word, checks it against null, and fails when it tries to convert "" to a number, with a ValueError. The writer should write the marker null for an empty tree, so the text is null and the reader returns None for the whole tree.

3. Write a function count_nodes(text) that counts the real nodes in a serialized text without building a tree. Test it on the text from exercise 1, where the answer is 6, and on the text null, where the answer is 0.

Show the answer

def count_nodes(text):
    return sum(1 for token in text.split(",") if token != "null")

Split the text on commas and count every word that is not null. Each real node contributes exactly one word, so the count is the number of nodes. For 8,3,1,null,null,null,10,null,14,13,null,null,null the function returns 6, and for null it returns 0.

4. A tree has 4 nodes. How many null markers does its text have? Give the count, and say why the rule holds for every tree.

Show the answer

The text has 5 markers. Each node has two child spots, so 4 nodes give 8 spots. The root is nobody's child, so only 3 spots hold real nodes, and the other 5 are empty. Every tree with n nodes has 2n - (n - 1), which is n + 1, empty spots, so its text has n + 1 markers.

5. Here is a text: 1,null,2. Say what the reader does with it, which exception it raises, and what the fix is.

Show the answer

The reader takes 1 as the root, then takes null as the left child, then takes 2 as the right child. It then tries to read the left child of 2, but the queue is empty, so popleft raises IndexError: pop from an empty deque. The text is missing two markers at the end, null,null, after 2. A complete text for this tree is 1,null,2,null,null, and the writer produces that text for a root with only a right child.

Summary

• Serializing a tree means writing it as text. Deserializing means rebuilding the tree from that text.
• A preorder list of values alone does not describe the shape. Write null at every empty spot to keep the shape.
• A tree with n nodes has n + 1 markers, so a text with the wrong count is damaged.
• The reader takes words from the front of a deque, so each call moves on to the next word without a position number.
• Test the round trip on empty, single-node, chain, zigzag, negative and duplicate-value trees, and check that the text is the same after the trip.
• Read the error message to find the cause: ValueError points to a bad word, and IndexError points to missing words.