Can someone plz expalin this coding interview problem

Question

This problem was asked by Google.

Given the root to a binary tree, implement serialize(root), which serializes the tree into a string, and deserialize(s), which deserializes the string back into the tree.

For example, given the following Node class

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

The following test should pass:

node = Node('root', Node('left', Node('left.left')), Node('right')) assert deserialize(serialize(node)).left.left.val == 'left.left'

Answer 1

What they are looking for, I expect, is that you can develop a traversal order that is reversible; that is, if you traverse the tree in pre-order fashion, then you get a string of output that you can build the tree back from fairly easily.

There's a good writeup I found here: http://interactivepython.org/courselib/static/pythonds/Trees/TreeTraversals.html showing how to do this.

I'm not a python coder (yet) but this problem is one that could be asked of a programmer in any language with objects or pointers (it would be harder in, say, SQL).