Serialize and Deserialize Binary Tree

December 25, 2023

Problem #

Design an algorithm to serialize a binary tree into a string and deserialize that string back into the original tree structure.

Solution #

To solve the problem of serializing and deserializing a binary tree, we can use a preorder traversal to serialize the tree. During serialization, we’ll represent null nodes as a specific marker (e.g., ‘X’). For deserialization, we can use the serialized string and rebuild the tree by following the order of elements.

Here’s a Python implementation for the problem:

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

def serialize(root):
    if root is None:
        return "#"
    else:
        return str(root.val) + ',' + serialize(root.left) + ',' + serialize(root.right)

def deserialize(data):
    def _deserialize_helper(values, i):
        if values[i] == "#":
            return None
        node = Node(int(values[i]))
        i += 1
        node.left = _deserialize_helper(values, i)
        i += 1
        node.right = _deserialize_helper(values, i)
        return node
    values = data.split(",")
    return _deserialize_helper(values, 0)



# Construct a binary tree
# Example:   1
#          /   \
#         2     3
#              / \
#             4   5
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.right.left = TreeNode(4)
root.right.right = TreeNode(5)

# Serialize
serialized = serialize(root)
print("Serialized Tree:", serialized)

# Deserialize
deserialized = deserialize(serialized)
# The deserialized tree is now reconstructed in 'deserialized'

In this solution:

• serialize() method is used to traverse the tree in pre-order way (root, left, right), and append each node value to a string with a ‘,’ separator. When it encounters a null node (indicated by “#”), it returns that symbol instead of going deeper into its children.

• deserialize() method is used to deserialize the string back into tree structure. It takes the serialized string and splits it into a list of strings where each string represents a node value or a “#” symbol. The _deserialize_helper() helper function then goes through this list, constructs each node one by one in pre-order manner, and connects them together as a tree structure.

Soultion analysis #

The algorithm used in the provided code for serializing and deserializing a binary tree is based on Depth-First Search (DFS), specifically a variant of preorder traversal.

Here’s a breakdown of how it uses DFS:

1. Serialization (DFS Preorder Traversal):

   • The serialize function traverses the binary tree in a preorder fashion (root, left, right).
   • For each node, it appends the node’s value to the string, followed by a delimiter (e.g., a comma).
   • If a node is null (representing the end of a branch), it appends a special marker (e.g., ‘#’) to the string.
   • This recursive process encodes the structure of the tree into a linear string format.

2. Deserialization:

   • The deserialize function uses the serialized string to rebuild the tree.
   • It splits the string into a list and processes each element sequentially.
   • For each non-null value, it creates a new node and recursively builds its left and right children.
   • The function follows the order provided by the preorder traversal in the serialized string, using recursion to rebuild the tree’s structure accurately.

The use of preorder traversal in DFS ensures that each node and its children are processed before moving to the next branch, which is crucial for accurately reconstructing the tree during deserialization.