Serialize and deserialize binary tree Here is my code of serialize and de-serialize a binary tree, looking for advice. One issue in my mind which I cannot resolve is, I am using a global variable index, wondering if more elegant solutions in Python 2.7 -- since in Python there is no solution to pass a reference as Java/C++ did. 

index = 0
class Node:
    def __init__(self, value, left, right):
        self.value = value
        self.left = left
        self.right = right
    @staticmethod
    def serialize(root, output):
        if not root:
            output.append('#')
            return
        output.append(root.value)
        Node.serialize(root.left, output)
        Node.serialize(root.right, output)
        return output
    @staticmethod
    def deserialize(source):
        global index
        if source[index] == '#':
            index += 1
            return None
        value = source[index]
        index += 1
        left = Node.deserialize(source)
        right = Node.deserialize(source)
        return Node(value, left, right)

if __name__ == "__main__":
    root = Node('a', Node('b', None, None), Node('c', Node('e', Node('g', None, None), None), Node('f', None, None)))
    result = []
    Node.serialize(root, result)
    print result
    new_root = Node.deserialize(result)
    result2 = []
    Node.serialize(new_root, result2)
    print result2
For starter, you don't need to use a global index. Python tuples make it easy to return several values at once, you can return the new index with the deserialized value:

    @staticmethod
    def deserialize(source):
        def _helper(index):
            if source[index] == '#':
                return None, index + 1

            value = source[index]
            left, index = _helper(index + 1)
            right, index = _helper(index)
            return Node(value, left, right), index
        return _helper(0)[0]


Now, what if I what to serialize the node Node('#', None, None)? I will get ['#', '#', '#'] as output that will get deserialized as None. Not that ideal. If you want to keep this intermediate format, you should at least allow the user to chose its sentinel value. Using a parameter with a default value in both serialize and `deserialize is a good option.

I would also improve the interface of your class: turning serialize into a method and deserialize into a classmethod. This allow for ease of use and easy subclassing:

class Node(object):
    ...

    def serialize(self, sentinel='#'):
        serial = [self.value]
        if self.left is None:
            serial.append(sentinel)
        else:
            serial.extend(self.left.serialize(sentinel))
        if self.right is None:
            serial.append(sentinel)
        else:
            serial.extend(self.right.serializr(sentinel))
        return serial

    @classmethod
    def deserialize(cls, source, sentinel='#'):
        def _helper(index):
            if source[index] == sentinel:
                return None, index + 1

            value = source[index]
            left, index = _helper(index + 1)
            right, index = _helper(index)
            return cls(value, left, right), index
        return _helper(0)[0]


And at the very last, I would provide default values for the left and right parameters:

class Node(object):
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right


So I can more easily write trees:

t = Node(13, Node(8), Node(15, right=Node(18)))
t.serialize()
# [13, 8, '#', '#', 15, '#', 18, '#', '#']




An other way to look at the problem is to take inspiration from repr. If we were to write an official representation for such objects, we could end up with:

    def __repr__(self):
        return '{}(value={!r}, left={!r}, right={!r})'.format(self.__class__.__name__, self.value, self.left, self.right)


And repr(t) would be the string:

Node(value=13, left=Node(value=8, left=None, right=None), right=Node(value=15, left=None, right=Node(value=18, left=None, right=None)))


It's a bit verbose, but it is serialized as a string. Using eval on this string would even deserialize it and return a Node equivalent to t. I however advise against the use of eval for deserialization purposes as it is too generic and thus dangerous.

Instead, serialization could return a more stripped form such as (8,,) for Node(8) or ('#',(5,,),) for Node('#', Node(5)) and deserialization would be a parser tailored for this representation.

Serialization is easy:

    def serialize(self):
        return '({!r},{},{})'.format(
            self.value,
            '' if self.left is None else repr(self.left),
            '' if self.right is None else repr(self.right))


Deserialization is left as an exercise for the reader.