How do you serialize and deserialize a binary tree?
You write the tree out as a list of values in a fixed order, with a marker for the places where there is no node.
class TreeNode:
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right
def serialize(root):
output = []
def walk(node):
if node is None:
output.append("None")
return
output.append(str(node.value))
walk(node.left)
walk(node.right)
walk(root)
return ",".join(output)
def deserialize(text):
parts = text.split(",")
index = 0
def build():
nonlocal index
part = parts[index]
index += 1
if part == "None":
return None
node = TreeNode(int(part))
node.left = build()
node.right = build()
return node
return build()
So how does it work? The serialize function does a depth first walk and writes down every node and every gap. The gap matters, because without it you could not tell a tree with one child from a tree with two children. So the empty sub-trees are written as the word "None".
the tree 1
/ \
2 3
the serialized form 1,2,None,None,3,None,None
And the deserialize function reads the parts back one at a time. When it reads a number it makes a node, and then it builds the left child and the right child by calling itself. When it reads the word "None" it gives back nothing, which ends that branch.
And the index variable is what makes this work. It says how far along the list of parts you have got. Every call takes the next part and moves the index on, and because the two recursive calls happen in the same order as the writing down, the parts come back in the right order.
And the complexity is O of n for the time and O of n for the space, because the string has one entry for every node and every gap.
So the rule to remember is this. You must write down the gaps as well as the nodes, or you cannot rebuild the tree.
The last question in this topic shows the breadth first version.