Python Program to Serialize and Deserialize Binary Tree

Use a class with serialize method to convert the tree to a string using preorder traversal and deserialize method to rebuild the tree from that string, for example: def serialize(root): return ' '.join(preorder) and def deserialize(data): return tree rebuilt from data.

Examples

Inputroot = None

OutputSerialized: '', Deserialized: None

Inputroot = TreeNode(1, TreeNode(2), TreeNode(3, TreeNode(4), TreeNode(5)))

OutputSerialized: '1 2 # # 3 4 # # 5 # #', Deserialized: Tree with same structure

Inputroot = TreeNode(10)

OutputSerialized: '10 # #', Deserialized: Tree with single node 10

How to Think About It

To serialize a binary tree, we visit nodes in preorder (root, left, right) and record their values, using a special marker like '#' for null children. To deserialize, we read the values in order and rebuild the tree by creating nodes or returning None when we see the marker.

Algorithm

1

Define a helper function to traverse the tree preorder and build a list of node values or '#' for nulls.

2

Join the list into a string separated by spaces to serialize.

3

Split the string back into a list for deserialization.

4

Define a helper function that reads the list and creates nodes recursively, returning None for '#'.

5

Return the rebuilt tree root.

Code

python

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

class Codec:
    def serialize(self, root):
        def preorder(node):
            if not node:
                vals.append('#')
                return
            vals.append(str(node.val))
            preorder(node.left)
            preorder(node.right)
        vals = []
        preorder(root)
        return ' '.join(vals)

    def deserialize(self, data):
        def build():
            val = next(vals)
            if val == '#':
                return None
            node = TreeNode(int(val))
            node.left = build()
            node.right = build()
            return node
        vals = iter(data.split())
        return build()

# Example usage
codec = Codec()
root = TreeNode(1, TreeNode(2), TreeNode(3, TreeNode(4), TreeNode(5)))
serialized = codec.serialize(root)
print('Serialized:', serialized)
deserialized = codec.deserialize(serialized)
print('Deserialized root value:', deserialized.val)

Output

Serialized: 1 2 # # 3 4 # # 5 # #
Deserialized root value: 1

Dry Run

Let's trace the example tree with root 1, left child 2, and right subtree 3 -> 4 and 5 through serialization and deserialization.

1

Serialize root node

vals = ['1']

2

Serialize left child (2)

vals = ['1', '2']

3

Serialize left child's left and right (None)

vals = ['1', '2', '#', '#']

4

Serialize right child (3)

vals = ['1', '2', '#', '#', '3']

5

Serialize 3's left child (4) and its children (None)

vals = ['1', '2', '#', '#', '3', '4', '#', '#']

6

Serialize 3's right child (5) and its children (None)

vals = ['1', '2', '#', '#', '3', '4', '#', '#', '5', '#', '#']

7

Deserialization starts reading '1'

Create node with val=1

8

Build left subtree from next values

Create node with val=2, then two '#' return None children

9

Build right subtree from next values

Create node with val=3, build left child 4, right child 5 with None children

Step	Serialized List	Action
1	['1']	Add root value
2	['1', '2']	Add left child
3	['1', '2', '#', '#']	Add null children for 2
4	['1', '2', '#', '#', '3']	Add right child
5	['1', '2', '#', '#', '3', '4', '#', '#']	Add left child of 3
6	['1', '2', '#', '#', '3', '4', '#', '#', '5', '#', '#']	Add right child of 3

Why This Works

Step 1: Why preorder traversal?

Preorder visits root before children, so we record node values in order and can rebuild the tree recursively.

Step 2: Why use '#' for null?

The '#' marks where a child is missing, so deserialization knows when to stop and return None.

Step 3: How deserialization works

We read values one by one; if '#', return None, else create node and recursively build left and right subtrees.

Alternative Approaches

Level-order (BFS) serialization

python

from collections import deque

class CodecBFS:
    def serialize(self, root):
        if not root:
            return ''
        queue = deque([root])
        res = []
        while queue:
            node = queue.popleft()
            if node:
                res.append(str(node.val))
                queue.append(node.left)
                queue.append(node.right)
            else:
                res.append('#')
        return ' '.join(res)

    def deserialize(self, data):
        if not data:
            return None
        vals = data.split()
        root = TreeNode(int(vals[0]))
        queue = deque([root])
        i = 1
        while queue:
            node = queue.popleft()
            if vals[i] != '#':
                node.left = TreeNode(int(vals[i]))
                queue.append(node.left)
            i += 1
            if vals[i] != '#':
                node.right = TreeNode(int(vals[i]))
                queue.append(node.right)
            i += 1
        return root

This method uses breadth-first traversal and can be easier to understand for some, but the serialized string may be longer with many '#' markers.

Using JSON to serialize

python

import json

def serialize(root):
    if not root:
        return 'null'
    return json.dumps({'val': root.val, 'left': serialize(root.left), 'right': serialize(root.right)})

def deserialize(data):
    if data == 'null':
        return None
    obj = json.loads(data)
    node = TreeNode(obj['val'])
    node.left = deserialize(obj['left'])
    node.right = deserialize(obj['right'])
    return node

This approach uses JSON format for readability and interoperability but is less space-efficient and slower.

Complexity: O(n) time, O(n) space

Time Complexity

Both serialization and deserialization visit each node once, so time is proportional to the number of nodes, O(n).

Space Complexity

The serialized string and recursion stack both use space proportional to the number of nodes, O(n).

Which Approach is Fastest?

Preorder traversal is simple and efficient; BFS uses queues and may produce longer strings; JSON is readable but slower and larger.

Approach	Time	Space	Best For
Preorder Traversal	O(n)	O(n)	Simple and fast serialization/deserialization
Level-order (BFS)	O(n)	O(n)	When breadth-first order is preferred
JSON Serialization	O(n)	O(n)	Readability and interoperability with other systems