Python Program to Serialize and Deserialize a Binary Tree

This program demonstrates how to serialize a binary tree into a string format and deserialize that string back into the original binary tree structure. The program uses a pre-order traversal for serialization and a marker (such as ‘None’) for null nodes to accurately preserve the tree structure, including its leaf nodes.

class TreeNode:
    """Definition for a binary tree node."""
    def __init__(self, x):
        """
        Initialize a tree node with a value.
        
        :param x: int, the integer value of the node
        """
        self.val = x
        self.left = None
        self.right = None

class Codec:
    """Codec for serializing and deserializing a binary tree."""
    
    def serialize(self, root):
        """
        Serializes a tree to a single string.
        
        :param root: TreeNode, the root of the binary tree
        :return: str, serialized format of the tree
        """
        def do_serialize(node):
            """Helper function for recursive pre-order serialization."""
            if node is None:
                return 'None,'
            return str(node.val) + ',' + do_serialize(node.left) + do_serialize(node.right)
        
        return do_serialize(root)
    
    def deserialize(self, data):
        """
        Deserializes your encoded data to tree.
        
        :param data: str, serialized string to be deserialized
        :return: TreeNode, the root of the deserialized binary tree
        """
        def do_deserialize(elements):
            """Helper function for recursive deserialization."""
            value = next(elements)
            if value == 'None':
                return None
            node = TreeNode(int(value))
            node.left = do_deserialize(elements)
            node.right = do_deserialize(elements)
            return node
        
        elements = iter(data.split(','))
        return do_deserialize(elements)

# Example Usage
if __name__ == "__main__":
    codec = Codec()
    tree = TreeNode(1)
    tree.left = TreeNode(2)
    tree.right = TreeNode(3)
    tree.right.left = TreeNode(4)
    tree.right.right = TreeNode(5)

    serialized = codec.serialize(tree)
    print("Serialized tree:", serialized)

    deserialized = codec.deserialize(serialized)
    print("Deserialized tree root value:", deserialized.val)

The Codec class contains two methods: serialize which converts the binary tree into a comma-separated string using a pre-order traversal where ‘None’ indicates a null node, and deserialize, which converts the string back into a binary tree using the same pre-order information. The use of generators and recursion makes the deserialization efficient and straightforward.