The problem
Write two functions. serialize(root) turns a binary tree into a string. deserialize(data) turns that string back into a tree with exactly the same shape and values. You choose the format.
s = serialize(root)
deserialize(s)
For example, serialize might return '1 2 # # 3 4 # # 5 # #', and deserialize of that string must build a new tree that is the same as root.
Values are whole numbers, possibly negative or with several digits, and may repeat. The tests only check that the round trip gives back the same tree, and that serialize returns a string.
The tests write a tree as a level-order list: the values level by level, left to right, with None where a child is missing. So [3, 9, 20, None, None, 15, 7] is 3 with children 9 and 20, where 20 has children 15 and 7. An empty tree is None.
Limits
- Up to 100,000 nodes, at most 300 levels deep, so recursion is fine.
Builds on TREE-7 Serialisation.
Continue on a laptop
Practice runs Python in the browser and needs a keyboard and a wider screen. Read the problem and open hints here, then write your solution on a laptop. Progress is saved per browser for now, so hints opened here stay on this device.
Need a hint?0 of 3 opened
- Hint 1Nudge
- Hint 2Approach Open hint 1 first
- Hint 3Pseudocode Open hint 2 first
- Worked solutionlast resort Opens after all 3 hints
Ctrl + Enter runs the tests. Tab indents; press Esc, then Tab, to leave the editor.
| # | Test | Result | Reads · time |
|---|---|---|---|
| 1 | Small tree | Not run | |
| 2 | Empty tree | Not run | |
| 3 | One node | Not run | |
| 4 | Long and negative values | Not run | |
| 5 | Same values, different shapes | Not run | |
| 6 | Path 300 deep | Not run | |
| 7 | 100,000 nodes | Not run |