How would you serialize and deserialize a binary tree?

Serializing a binary tree involves converting the binary tree into a string representation that can be easily stored or transmitted. Deserializing involves reconstructing the tree from the stored string representation. For this example, let’s define a binary tree node as follows:

class Node:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

**Serialization**

One common way to do this is to perform a depth-first pre-order traversal of the original tree, converting each node’s value into a string on the go.

def serialize(self, root):
    """Encodes a tree to a single string.
       
       :type root: TreeNode
       :rtype: str
    """
    if root is None:
        return 'None,'
    return str(root.val) + ',' + self.serialize(root.left) + self.serialize(root.right)

The function ‘serialize‘ is recursive. Notice that if the node is None (leaf node), it returns ’None,’. This is useful for identifying leaf nodes during deserialisation.

**Deserialization**

To deserialize, we’ll break the string apart with ’,’ as the delimiter. When constructing the binary tree, we’ll remove values from the list and traverse the tree in the same pre-order that we used when serializing.

Here’s the code:

def deserialize(self, data):
    """Decodes your encoded data to tree.
       
       :type data: str
       :rtype: TreeNode
    """
    def helper(data_list):
        if data_list[0] == 'None':
            data_list.pop(0)
            return None
        node = Node(int(data_list[0]))
        data_list.pop(0)
        node.left = helper(data_list)
        node.right = helper(data_list)
        return node

    data_list = data.split(',')
    return helper(data_list)

The function ‘helper‘ is recursive. It pops the first element from ‘data_list‘ and uses that to create a new TreeNode ‘node‘, does the same for ‘node.left‘ and ‘node.right‘, and finally returns ‘node‘.

In this method, the time complexity is O(n) for both serialization and deserialization, where n is the number of nodes. This is because we visit each node exactly once. The space complexity is also O(n) because in the worst case (i.e., the tree is completely unbalanced, like a linked list), the call stack could be n layers deep.