Save and Restore a Tree

#172 · Trees · Expert · 195 XP · about 35 min

To store a binary tree in a file or send it over a network, you turn it into text, and later you rebuild the tree from that text. Write a class TreeCodec with two methods:

serialize(self, root) returns a string that describes the whole tree.
deserialize(self, text) takes such a string and returns the root of a tree with the same shape and the same values (None for an empty tree).

You design the text format: the tests check only that it is a string, that equal trees give equal text, and that it turns back into an identical tree, even when a new TreeCodec reads it. Write both directions yourself, without calling the provided build and to_list, which are there for the tests.

Examples

codec = TreeCodec()
text = codec.serialize(build([7, 3, 9, None, 4, 8]))
isinstance(text, str)  # returns True
to_list(codec.deserialize(text))  # returns [7, 3, 9, None, 4, 8]
to_list(codec.deserialize(codec.serialize(build([]))))  # returns []

The tree build([7, 3, 9, None, 4, 8]) survives the round trip unchanged, and so does the empty tree.

Constraints

0 to 2,000 nodes. Values are integers from -1,000 to 1,000, so they can be negative or have several digits.
Values can repeat.

Note

Each node is a Node with a value val and two children, left and right.
Two trees that hold the same values in different shapes must give different text.

# Provided: do not change

from collections import deque

class Node:

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

self.val = val

self.left = left

self.right = right

def build(values):

"""Build a tree from a level-order list; None marks a missing child."""

if not values or values[0] is None:

return None

root = Node(values[0])

queue = deque([root])

i = 1

while queue and i < len(values):

node = queue.popleft()

if values[i] is not None:

node.left = Node(values[i])

queue.append(node.left)

i += 1

if i < len(values) and values[i] is not None:

node.right = Node(values[i])

queue.append(node.right)

i += 1

return root

def to_list(root):

"""The tree as a level-order list, without trailing None values."""

values, queue = [], deque([root])

while queue:

node = queue.popleft()

if node is None:

values.append(None)

else:

values.append(node.val)

queue.append(node.left)

queue.append(node.right)

while values and values[-1] is None:

values.pop()

return values

class TreeCodec:

def serialize(self, root):

# Your code here

pass

def deserialize(self, text):

# Your code here

pass

codec = TreeCodec()

print(to_list(codec.deserialize(codec.serialize(build([7, 3, 9, None, 4, 8])))))

Ready?

Accept the challenge to start writing. A small timer counts the time this page is in view.

Output appears here.