Serialize and deserialize binary tree with a lot of empty nodes
I would use a map mapping each key of a node \$u\$ in the tree to a 2-tuple containing the key of the parent \$p\$, and a boolean indicating whether \$u\$ is a left or right child of \$p\$:

class TreeNode:

    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None

    def __eq__(self, other):
        return self.key == other.key

    def __hash__(self):
        return self.key


def serialize_tree(root_node):
    map_node_key_to_parent_data = {}

    def serialize_tree_impl(node, parent_node):
        if parent_node:
            parent_data = (parent_node.key, parent_node.left is node)
            map_node_key_to_parent_data[node.key] = parent_data
        else:
            map_node_key_to_parent_data[node.key] = None

        if node.left:
            serialize_tree_impl(node.left, node)

        if node.right:
            serialize_tree_impl(node.right, node)

    serialize_tree_impl(root_node, None)
    return map_node_key_to_parent_data


def deserialize_tree(map_node_key_to_parent_data):
    map_node_key_to_tree_node = {}

    for node_key in map_node_key_to_parent_data.keys():
        if node_key not in map_node_key_to_tree_node.keys():
            map_node_key_to_tree_node[node_key] = TreeNode(node_key)
        else:
            raise TypeError("Duplicate node in the tree.")

    root_node = None

    for node_key, parent_data in map_node_key_to_parent_data.items():
        node = map_node_key_to_tree_node[node_key]

        if not parent_data:
            root_node = node
        else:
            parent_node_key = parent_data[0]
            on_left = parent_data[1]
            parent_node = map_node_key_to_tree_node[parent_node_key]

            if on_left:
                parent_node.left = node
            else:
                parent_node.right = node

    return root_node


def binary_search_trees_are_identical(root_node1, root_node2):
    if not root_node1 and not root_node2:
        return True

    if not root_node1 or not root_node2:
        return False

    if root_node1.key != root_node2.key:
        return False

    return binary_search_trees_are_identical(root_node1.left, root_node2.left)\
        and binary_search_trees_are_identical(root_node2.right, root_node2.right)


def main():
    root_node = TreeNode(5);
    l = TreeNode(3)
    r = TreeNode(7)
    rr = TreeNode(10)
    lr = TreeNode(4)
    rrl = TreeNode(11)
    rr.left = rrl

    root_node.left = l
    root_node.right = r
    l.right = lr
    r.right = rr

    serialized_tree = serialize_tree(root_node)
    print serialized_tree

    deserialized_tree_root_node = deserialize_tree(serialized_tree)
    print "Trees are identical:", binary_search_trees_are_identical(root_node, deserialized_tree_root_node)
    pass


if __name__ == "__main__":
    main()


A bug?

On 

root = TreeNode(1, TreeNode(2, TreeNode(3, TreeNode(4, TreeNode(5, None, None), None), None), None), None)


I get an IndexError.

Hope that helps.