Start learning free

LESSON 418 OF 536 · BINARY TREES

Serialize and Deserialize a Binary Tree in Python: O(n) Preorder

Practice O(n) Read the full explanation

Serializing a tree turns it into a string, so it can be saved in a file or sent over a network. Deserializing rebuilds the same tree from that string.

Implement the class Codec:

serialize(root) gets the root of a binary tree, which may be empty, and returns a string.
deserialize(data) gets a string made by serialize and returns the root of the same tree: the same shape, with the same value in every node.

The string's format is up to you. The tests serialize each tree with one Codec, rebuild it with a second Codec's deserialize, and print the rebuilt tree level by level, from left to right, with null where a child is missing and the trailing nulls left out. The trees below are written the same way. serialize must return a string. The starter code spells these names the way your language does.

Example 1:

Input: root = [1,2,3,null,null,4,5]
Output: [1,2,3,null,null,4,5]
    1
   / \
  2   3
     / \
    4   5

Explanation: One string that works lists the nodes in preorder, with # for a missing child: "1,2,#,#,3,4,#,#,5,#,#". Reading it back gives the same tree.

Example 2:

Input: root = []
Output: []
Explanation: The empty tree needs a string too, for example "#", and deserialize gives back an empty tree.

Example 3:

Input: root = [-1,0,null,null,-100]
Output: [-1,0,null,null,-100]
    -1
    /
   0
    \
   -100

Explanation: Values can be negative and have several digits. With commas between the pieces, as in "-1,0,#,-100,#,#,#", every value is read back whole.

Constraints:

The number of nodes in the tree is in the range [0, 2 * 10⁵].
Each node value is between -1000 and 1000.
The tree is at most 400 levels deep.

Note:

Both serialize and deserialize should run in O(n) time, where n is the number of nodes.

STEP 1 OF 19

Guided

Ctrl + Enter to check

PYTHON · BINARY TREES

Serialize And Deserialize Binary Tree in Python, explained

Problem overview

The class Codec has two methods. serialize(root) takes the root of a binary tree, which may be empty (None), and returns a string. deserialize(data) takes a string made by serialize and returns the root of the same tree, with the same shape and the same value in every node. The format of the string is up to you. The lesson provides the TreeNode class: TreeNode(x) sets val to x and left and right to None.

The tests serialize a tree with one Codec and rebuild it with the deserialize of a second one, so the string has to carry everything. Nothing may be remembered in the object between the two calls.

Approach: preorder with markers for missing children

A list of values alone is not enough to rebuild a tree, because many different trees share the same preorder list. The fix is to write down the empty children too. Walk the tree in preorder (a node, then its left subtree, then its right subtree), write # for every None, and put a comma between the pieces. The tree with root 1 and children 2 and 3 becomes 1,2,#,#,3,#,#.

The markers say exactly where each subtree ends: after a node's piece, the reader takes one whole subtree for its left child, then one whole subtree for its right child. A # is the smallest possible subtree, an empty one. This makes the string enough to rebuild the tree with a recursion that mirrors the one that wrote it.

The commas matter because values can have several digits and a minus sign. Without them, 1 followed by 2 and the single value 12 would write the same text. With them, split(",") cuts the string back into the original pieces.

For the second example's tree, [1,2,3,null,null,4,5], the string is 1,2,#,#,3,4,#,#,5,#,#. The empty tree is the string #. The tree [-1,0,null,null,-100] gives -1,0,#,-100,#,#,#.

Step by step

Writing the tree

Start a list of pieces in serialize as an attribute, self.values = [], so the helper can add to it.
Call the helper self.write(root). It appends the pieces of the whole tree in preorder.
Join the pieces into one string with ",".join(self.values).
Declare the helper write(self, node). It adds the pieces of the subtree under node.
Mark a missing child. If node is None, append "#".
Return right after the marker: an empty child has nothing under it.
Write the node's value as text, str(node.val). The node comes first, which is what makes it preorder.
Write the left subtree by calling self.write(node.left).
Write the right subtree by calling self.write(node.right).

Reading it back

Cut the string into pieces with data.split(",") and store the list in self.values.
Start a position counter self.pos at 0, the first piece.
Return what self.read() gives. Called here, it reads one whole subtree, which is the whole tree.
Declare the helper read(self). It reads the subtree that starts at self.pos and returns its root.
Take the next piece as value = self.values[self.pos] and move self.pos forward by one. Each piece is read exactly once.
An empty child. If value is "#", return None.
A real node. Otherwise create TreeNode(int(value)). int understands a leading minus sign, so negative values come back whole.
Read the left subtree with node.left = self.read(). It consumes all the pieces of the left subtree, markers included, and stops where the right subtree begins.
Read the right subtree with node.right = self.read(). Now self.pos is just past this node's whole subtree.
Return the node.

The solution in Python

class Codec:
    def write(self, node):
        if node is None:
            self.values.append("#")
            return
        self.values.append(str(node.val))
        self.write(node.left)
        self.write(node.right)

    def serialize(self, root: Optional[TreeNode]) -> str:
        self.values = []
        self.write(root)
        return ",".join(self.values)

    def read(self):
        value = self.values[self.pos]
        self.pos += 1
        if value == "#":
            return None
        node = TreeNode(int(value))
        node.left = self.read()
        node.right = self.read()
        return node

    def deserialize(self, data: str) -> Optional[TreeNode]:
        self.values = data.split(",")
        self.pos = 0
        return self.read()

Python details worth a closer look:

join needs strings. ",".join(self.values) raises TypeError if the list holds integers, which is why write appends str(node.val) instead of node.val.
join and split are opposites. ",".join(["1", "2", "#"]) gives "1,2,#", and "1,2,#".split(",") gives ['1', '2', '#']. For "#", split returns the list ['#'], so the empty tree reads back as None without a special case.
One attribute, two meanings. self.values holds the pieces being written in serialize and the pieces being read in deserialize. Each method starts by assigning it fresh, so reusing one Codec object for several trees works: calling serialize on [1,2] and then on [3] gives 1,2,#,#,# and 3,#,#.
The counter lives on self. self.pos advances across all the recursive calls of read. A local variable would reset in every call and the reads would overlap.
is None. In write, node is None is the idiomatic test for a missing child.
Recursion depth. Trees here are at most 400 levels deep, within Python's default recursion limit of 1,000.

Complexity

Time: O(n) for both methods, where n is the number of nodes. A tree with n nodes has n + 1 empty children, so the string has 2n + 1 pieces. write and read each handle every piece once with constant work, and join and split are linear in the length of the text.

Space: O(n). The list of pieces and the string both grow with n, and the recursion stack is as deep as the tree is tall.

Edge cases and common mistakes

The empty tree. It needs a string too: "#". Returning "" would break deserialize, because "".split(",") is [''], and that piece is neither "#" nor a number.
Leaving out the missing-child markers. Then [1,2] (2 on the left) and [1,null,2] (2 on the right) would both be written as 1,2, and the reader could not tell them apart.
Leaving out the commas. Values such as -100 or 12 would run together with their neighbours.
Reading the left before the right. The two reads in read must stay in the same order as the two writes in write. Swapping only one of them rebuilds a mirrored or broken tree.
Passing data between objects. deserialize must rely on data alone. It cannot read self.values from an earlier serialize, because the tests use a different Codec for it.

Testing

For each tree, serialize gave the string shown, and deserialize on that string gave the same tree back:

[1,2,3,null,null,4,5] gives 1,2,#,#,3,4,#,#,5,#,#.
[] gives #.
[-1,0,null,null,-100] gives -1,0,#,-100,#,#,#.
[7] gives 7,#,#.
[1,2] gives 1,2,#,#,#.

Keep going with Python500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free