Serializing and Deserializing Binary Tree

Prereq: DFS on Tree

Given a binary tree, write a serialize function that converts the tree into a string and a deserialize function that converts a string to a binary tree. You may serialize the tree into any string representation you want as long as it can be deseralized.

Try it yourself

Explanation

To serialize, we can simply do a DFS and append the node value to the string. We need to encode null nodes too since otherwise, we wouldn't be able to tell if we have reached leaf nodes when we deserialize. We use x here as a placeholder for the null node.

To deserialize, we split the string into tokens and consume them. For each token we create a new node using the token value. When we see an x, we know we reached the leaf and return.

Serialize

Deserialize

1class Node:
2    def __init__(self, val, left=None, right=None):
3        self.val = val
4        self.left = left
5        self.right = right
6
7def serialize(root):
8    res = []
9    def dfs(root):
10        if not root:
11            res.append('x')
12            return
13        res.append(root.val)
14        dfs(root.left)
15        dfs(root.right)
16    dfs(root)
17    return ' '.join(res)
18
19def deserialize(s):
20    def dfs(nodes):
21        val = next(nodes)
22        if val == 'x': return
23        cur = Node(int(val))
24        cur.left = dfs(nodes)
25        cur.right = dfs(nodes)
26        return cur
27    # create an iterator that returns a token each time we call `next`
28    return dfs(iter(s.split()))
29
30if __name__ == '__main__':
31    def build_tree(nodes):
32        val = next(nodes)
33        if not val or val == 'x': return
34        cur = Node(val)
35        cur.left = build_tree(nodes)
36        cur.right = build_tree(nodes)
37        return cur
38    def print_tree(root):
39        if not root:
40            yield "x"
41            return
42        yield str(root.val)
43        yield from print_tree(root.left)
44        yield from print_tree(root.right)
45    root = build_tree(iter(input().split()))
46    new_root = deserialize(serialize(root))
47    print(' '.join(print_tree(new_root)))
48