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 token value. When we see an x
we know we reached the leaf and return.
Serialize
Deserialize
Expand 4 lines ... | |||||
5 | 5 |
| |||
6 | 6 | ||||
7 | 7 |
| |||
8 | - |
| |||
8 | + |
| |||
9 | + |
| |||
10 | + |
| |||
11 | + |
| |||
12 | + |
| |||
13 | + |
| |||
14 | + |
| |||
15 | + |
| |||
16 | + |
| |||
17 | + |
| |||
18 | + | ||||
9 | 19 |
| |||
10 | - |
| |||
20 | + |
| |||
21 | + |
| |||
22 | + |
| |||
23 | + |
| |||
24 | + |
| |||
25 | + |
| |||
26 | + |
| |||
27 | + |
| |||
28 | + |
| |||
29 | + | ||||
11 | 30 |
| |||
12 | 31 |
| |||
13 | 32 |
| |||
14 | 33 |
| |||
15 | 34 |
| |||
Expand 14 lines ... |