Serialize and deserialize binary tree

Question

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

• Grajdeanu Alex: "since in Python there is no solution to pass a reference". Where did you read this ?
• Alex: You can use class attribute for storing index that which is also sort of global variable, but at least it's stored under class namespace.
• Lin Ma: @Alex, sounds good idea. If you could add a reply, I will mark it as answer to benefit other people. Also wondering if possible to do BFS other than DFS for serialize/deserialize?
• Lin Ma: @Dex'ter, could you show me how to pass int in Python by reference? Tried to search something failed.

Answer 1

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.

• Lin Ma: Thanks Mathias, love your comments and vote up. Is there a solution using BFS (serialize tree layer by layer) other than DFS (or pre-order traverse as we did now) for serialize and de-serialize?
• Lin Ma: BTW, also wondering if you have good ideas how store None as #? Suppose the tree is not very balanced, there will be a lot #. Correct?

Answer 2

This is for Python 3 only. You can have the simplicity of a global variable without actually having a global variable, by using an inner function. You'd have to declare the variable as nonlocal so that the inner function doesn't attempt to create another one.

def deserialize(self, data):
 source = data.split(',')
 index = 0
 def helper():
 nonlocal index
 if source[index] == '#':
 index += 1
 return None
 node = TreeNode(int(source[index]))
 index += 1
 node.left, node.right = helper(), helper()
 return node
 return helper()

• Toby Speight: Welcome to Code Review! You have presented an alternative solution, but haven't reviewed the code. Please edit to show what aspects of the question code prompted you to write this version, and in what ways it's an improvement over the original. It may be worth (re-)reading How to Answer.