Card 07/ 08
Practice: Saving a Tree as One Line and Rebuilding It
Write a tree out as one line of values with a marker for every missing child, then read the line back into the same tree.
Saving a tree as one line, so it can be stored in a file or sent over a network and rebuilt later, is called serialisation, and it combines passing values down a tree with reading it level by level. Take the tree 6, whose left child 2 has only a right child, 5, and whose right child 9 has only a left child, 7. Write it as one line of values in preorder, the node before its left subtree and its left subtree before its right, with # for every missing child. Then write the function that reads such a line and rebuilds the same tree, and say why the markers are needed. Finally, write the same tree in level order with a queue.
Show the answer and a solution
The preorder line is 6 2 # 5 # # 9 7 # # #: five values and six markers, since a tree of n nodes always has n + 1 empty children. Reading it back is recursion again. Each call takes the next item from the line; a # means an empty child and the call returns nothing, and a value becomes a node whose left subtree is built by the next call and its right subtree by the one after, so each call returns the subtree it built.
6, first in the line
2
null, written as #
5, two # follow it
9
7, two # follow it
null, written as #, the last item
The listing writes the line, rebuilds the tree from it and writes the copy, then writes the tree in level order, and last shows two trees whose lines agree without markers.
from collections import deque
from collections.abc import Iterator
class Node:
def __init__(self, value: int, left: Node | None = None, right: Node | None = None) -> None:
self.value = value
self.left = left
self.right = right
def write(node: Node | None, out: list[str]) -> list[str]:
if node is None:
out.append("#")
return out
out.append(str(node.value))
write(node.left, out)
write(node.right, out)
return out
def rebuild(tokens: Iterator[str]) -> Node | None:
token = next(tokens)
if token == "#":
return None
node = Node(int(token))
node.left = rebuild(tokens)
node.right = rebuild(tokens)
return node
def write_level_order(root: Node | None) -> list[str]:
out: list[str] = []
queue = deque([root])
while queue:
node = queue.popleft()
if node is None:
out.append("#")
continue
out.append(str(node.value))
queue.append(node.left)
queue.append(node.right)
while out and out[-1] == "#":
out.pop()
return out
tree = Node(6, Node(2, None, Node(5)), Node(9, Node(7)))
line = " ".join(write(tree, []))
print("preorder: ", line)
copy = rebuild(iter(line.split()))
print("rebuilt: ", " ".join(write(copy, [])))
print("level order:", " ".join(write_level_order(tree)))
left_only, right_only = Node(1, Node(2)), Node(1, None, Node(2))
print("without markers:", " ".join(v for v in write(left_only, []) if v != "#"), "and", " ".join(v for v in write(right_only, []) if v != "#"))
print("with markers: ", " ".join(write(left_only, [])), "and", " ".join(write(right_only, [])))preorder: 6 2 # 5 # # 9 7 # # #
rebuilt: 6 2 # 5 # # 9 7 # # #
level order: 6 2 9 # 5 7
without markers: 1 2 and 1 2
with markers: 1 2 # # # and 1 # 2 # #The rebuilt tree writes the same line, so it is the same tree. Without markers, a root 1 with a left child 2 and a root 1 with a right child 2 both write 1 2, and no reader could tell which was meant; with them, every value's position is fixed. In level order the queue takes children as it meets them, giving 6 2 9 # 5 7 once the trailing markers are dropped, since they carry nothing a reader needs. Writing and rebuilding are O(n) time and O(n) space for the line.
← → move through sections and cards